[CF1375E] Inversion SwapSort

[题目链接]

https://codeforces.ml/contest/1375/problem/E

[题解]

从小到大考虑 ， 对于当前位置 ， 找出所有 (j) 使得 (A_{j} < A_{i})。

将其按照权值为第一关键字 ， 下标为第二关键字降序排列。

那么依次交换即可。

这个构造的正确性在于每次将排名为 (i) 的数恰好放在了 (i) 号位置 ， 并且使得其它位置相对大小关系不变。

时间复杂度 : (O(N ^ 2logN))

[代码]

#include<bits/stdc++.h>

using namespace std;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)
#define mp make_pair

typedef long long LL;

const int MN = 3e6 + 5;

int N , A[MN];

int main() {
		
		scanf("%d" , &N);
		vector < pair < int , int > > ans;
		for (int i = 1; i <= N; ++i) scanf("%d" , &A[i]);
		for (int i = 1; i <= N; ++i) {
				vector < int > p;
				for (int j = i + 1; j <= N; ++j)
						if (A[j] < A[i]) p.emplace_back(j);
				sort(p.begin() , p.end() , [&] (int x , int y) {
					  if (A[x] != A[y]) return A[x] > A[y];
						else return x > y;
				}); 
				for (auto x : p) ans.emplace_back(mp(i , x));
		}
		printf("%d
" , (int) (ans.size()));
		for (int i = 0; i < ans.size(); ++i) 
				printf("%d %d
" , ans[i].first , ans[i].second);
	  return 0;
}