#include <iostream> #include <vector> #include <queue> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> V(n); for (auto& v : V) cin >> v; vector<vector<int>> G(n); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (V[j] < V[i]) { G[i].push_back(j); G[j].push_back(i); } } } for (int i = 0; i < n; i++) { queue<int> Q; Q.push(i); vector<int> dist(n, INT32_MAX); dist[i] = 0; while (Q.size()) { auto u = Q.front(); Q.pop(); for (auto& v : G[u]) { if (dist[v] == INT32_MAX) { dist[v] = dist[u] + 1; Q.push(v); } } } int sum = 0; for (auto& d : dist) if (d != INT32_MAX) sum += d; cout << sum << ' '; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <iostream> #include <vector> #include <queue> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> V(n); for (auto& v : V) cin >> v; vector<vector<int>> G(n); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (V[j] < V[i]) { G[i].push_back(j); G[j].push_back(i); } } } for (int i = 0; i < n; i++) { queue<int> Q; Q.push(i); vector<int> dist(n, INT32_MAX); dist[i] = 0; while (Q.size()) { auto u = Q.front(); Q.pop(); for (auto& v : G[u]) { if (dist[v] == INT32_MAX) { dist[v] = dist[u] + 1; Q.push(v); } } } int sum = 0; for (auto& d : dist) if (d != INT32_MAX) sum += d; cout << sum << ' '; } } |