新系列，系列名叫垫底模拟，厉害吧
T1 排序
最开始想的都是很简单的东西，就是把最大的数放到最后嘛，然后发现显然不行，比如说：
hack:
input:
5
1 5 3 2 4
output:
3 4
2 5
2 4
2 3
题目很明显地告诉我们先输出逆序对数 \(m\) 再输出交换 \(m\) 行操作，这 \(m\) 次操作还必须针对我们求出的逆序对，怎么能直接把最大数放到最后捏？
然后冒泡也不行，因为你冒泡交换的一定是相邻的坐标，根本不是针对我们逆序对交换的。
拿上面的例子说：
这个题不是让我们 \(sort\) 然后输出怎么 \(sort\) 的，而是让我们真的交换所有逆序对而且最后结果也必须保持升序。
于是我思考是酱紫的：如果说，\((i,i+1)\) 与 \((i+1,i+2)\) 都是逆序对，优先交换 \((i+1,i+2)\)，例如上面的数据 \(5,3,2\)。（当时感到非常得意，感觉马上就要AC）
然后就保龄了。
于是我们赛后重新理一下思路：
-
对于一个排列，排列不会出现重复数，所以每个数最终的位置是已知的。
-
考虑每组逆序对交换的顺序，因为我们要进行 \(m\) 次交换操作，所以我们的每次交换只能减少一次逆序对个数，要不然一定会少操作。
-
我们可以通过类似离散化的方式得到每个数的大小排名。
然后考虑交换顺序问题：
拿上面的数据来举例：
| \(sort\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(a=\) | \(1\) | \(5\) | \(3\) | \(4\) | \(2\) |
对于 \(a=\) \(5>3,5>4\) 来说，我们应当优先交换 \(a(5,3)\)，这样的话 \(a=5\) 仍在 \(a=4\) 前，否则就少了逆序对个数。
交换后：
| \(sort\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(a=\) | \(1\) | \(3\) | \(5\) | \(4\) | \(2\) |
对于 \(temp\) \(5>2,4>2\) 来说，我们应当优先交换 \(a(4,2)\)，这样的话 \(a=5\) 仍在 \(a=2\) 前，否则就少了逆序对个数。
因此得到重要结论：当逆序对第一个数相等时，优先交换下标较小数。
当逆序对第二个数相等时，优先交换下标较大数。
然后是洛谷的题需要判重复。
有代码：
Miku's Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+50;
int n,a[maxn],temp[maxn],ranking[maxn];
int sorta[maxn];
struct WORK{
int x;
int y;
};WORK w[maxn*1000];
int cnt;
bool cmp(WORK xx,WORK yy){
if(xx.x==yy.x){
if(ranking[xx.y]!=ranking[yy.y]) return ranking[xx.y]>ranking[yy.y];
return xx.y>yy.y;
}
return xx.x<yy.x;
}
void input(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
sorta[i]=a[i];
}
sort(sorta+1,sorta+1+n);
//int len=unique(sorta+1,sorta+1+n)-(sorta+1);
//len=n;
for(int i=1;i<=n;++i){
ranking[i]=lower_bound(sorta+1,sorta+1+n,a[i])-sorta;
}
}
void get(){
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(ranking[i]>ranking[j]){
++cnt;
w[cnt].x=i;
w[cnt].y=j;
}
}
}
}
int main(){
input();
get();
sort(w+1,w+1+cnt,cmp);
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i){
printf("%d %d\n",w[i].x,w[i].y);
}
return 0;
}