CF1375E 题解

题意

给定一个长度为 $n$ 的序列 $a$，求 $a$ 的逆序对数量，以及逆序对的一个排列，使得按排列顺序交换各个逆序对元素后，排列单调不降，如 3, 1, 2 -> 1, 3, 2 -> 1, 2, 3。

$1 \le n \le 10^3$，$1 \le a_i \le 10^9$

题解

构造题，先考虑 $a$ 为一个排列的情况，设 $b_{a_i} = i$，即每个元素在 $a$ 中的位置，我们可以将 $n$ 放到最后一个位置上，缩小问题规模。 最后一个位置上的数是 $a_n$，它与 $a_n + 1 ~ n$ 都构成了逆序对，那就可以一次交换 $(b_{a_n + 1}, n)$，$(b_{a_n + 1}, n)$ 一直到 $(b_{a_n}, n)$，这样不仅 $n$ 放到了最后一个位置，而且对于前面所有大于 $a_n$ 的数，都相当于值减了 $1$ ，也就是相对位置不变，成功缩小了问题规模，这样就可以一直做到 $1$ 解决问题，时间复杂度 $O(n^2)$。

解决了 $a$ 为排列的情况后就很简单了。可以以 $a_i$ 为第一关键字，$i$ 为第二关键字排序后哈希，这样逆序对与原排列相同，就可以直接解决了。

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read();
#define N 1010

int n, a[N], c[N], sum = 0;
pair<int, int> b[N];

int main() {
	n = read();
	for (int i = 1; i <= n; i ++) {
		a[i] = read(), b[i] = make_pair(a[i], i);
	}
	sort(b + 1, b + n + 1);
	for (int i = 1; i <= n; i ++) {
		a[b[i].second] = i, c[i] = b[i].second;
	}

	for (int i = 1; i <= n; i ++) {
		for (int j = i + 1; j <= n; j ++) {
			if (a[i] > a[j]) sum ++;
		}
	}
	printf("%d\n", sum);

	for (int i = n; i >= 1; i --) {
		for (int j = a[i] + 1; j <= i; j ++) {
			int t = c[j];
			c[a[t]] = i, c[a[i]] = t;
			swap(a[t], a[i]);
			printf("%d %d\n", t, i);
		}
	}
	return 0;
}

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}