题解
对于相邻的两个数 (a_i, a_{i+1}),如果 (a_i > a_{i+1}) 那么就交换两个数。最后反着做一遍。
先给出代码 :
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j; i <= k; i++)
using namespace std;
const int N = 1123;
int a[N], b[N], n, tot, stk[N * N][2];
int main() {
scanf("%d", &n);
L(i, 1, n) scanf("%d", &a[i]), b[i] = i;
L(i, 1, n) L(j, 1, n - 1) if(a[j] > a[j + 1]) swap(a[j], a[j + 1]), ++tot, stk[tot][0] = b[j], stk[tot][1] = b[j + 1], swap(b[j], b[j + 1]);
printf("%d
", tot);
while(tot) printf("%d %d
", stk[tot][0], stk[tot][1]), --tot;
return 0;
}
这为什么是对的呢?
我们可以把原序列 (a) 视作一个置换(例:1 1 2 2 1
变成 3 2 5 4 1
),然后求出他的逆置换 (b)(即每一个数要到达哪个数)
如果我们交换了 (a_{u}) 和 (a_{v}),那么 (b_{a_u}) 和 (b_{a_v}) 也会交换。
我们把冒泡排序反了过来,每次交换的一定是值相邻的数(?)而且形成一个逆序对,所以这么做是对的。