fork download
copy 
  1. /*
  2. given:
  3. - a permutation from 1 to n.
  4. - for each i, you can choose to change a_i to 2 * n - a_i
  5. solve: 
  6. - find lowest # of inversions
  7.  
  8. hint 1: 
  9. - inversions containing i if a_i = 1 are # of indices to the left of i.
  10. - inversions containing i if a_i = 2 * n - 1 are # of indices to the right of i.
  11. - so we can uniquely determine whether or not a_i = 1 should be flipped or not.
  12.  
  13. - can we then do this for 2, and then 3, and so on?
  14. */
  15. #include <iostream>
  16. #include <vector>
  17. #include <map>
  18. #include <set>
  19. using namespace std;
  20.  
  21. int main() {
  22. 	cin.tie(0)->sync_with_stdio(0);
  23. 	int t; cin >> t;
  24. 	while (t--) {
  25. 		int n; cin >> n;
  26. 		vector<int> a(n);
  27. 		for (int &x : a) cin >> x;
  28. 		map<int, int> pos;
  29. 		for (int i = 0; i < n; i++) {
  30. 			pos[a[i]] = i;
  31. 		}
  32. 		int ans = 0;
  33. 		set<int> taken;
  34. 		for (int i = 1; i <= n; i++) {
  35. 			int x = pos[i];
  36. 			int flip = 0, not_flip = 0;
  37. 			for (int j = 0; j < x; j++) {
  38. 				if (a[j] > i && !taken.count(j)) flip++;
  39. 			}
  40. 			for (int j = x + 1; j < n; j++) {
  41. 				if (a[j] > i && !taken.count(j)) not_flip++;
  42. 			}
  43. 			ans += min(flip, not_flip);
  44. 			taken.insert(x);
  45. 		}
  46. 		cout << ans << '\n';
  47. 	}
  48. }
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
2
2 1
3
2 1 3
4
4 3 2 1
5
2 3 1 5 4
6
2 3 4 1 5 6
stdout
copy 
0
1
0
2
2
https://ideone.com/P6PDSI
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!