海亮01/10构造专题
T1
题意
给定一个长度为 \(n\) 的序列 \(a\)，求 \(a\) 中的所有逆序对 \((i_1, j_1), (i_2, j_2), \cdots, (i_m, j_m)\) 的一个排列 \(p\)，
使得依次交换 \((a_{i_{p_1}}, a_{j_{p_1}}), (a_{i_{p_2}}, a_{j_{p_2}}), \cdots, (a_{i_{p_m}}, a_{j_{p_m}})\) 后序列单调不降。
\(1 \le n \le 10^3\)，\(1 \le a_i \le 10^9\)。
题解
先将原数组从小到大编号（如果两个数大小相同，那么按照下标从小到大编号）变成排列 \(b\)。
我们可以想到，每次考虑将最左边的位置 \(i\) 进行交换使得满足以下两条：
- 让位置 \(i\) 最终填上数字 \(i\)。
- 不改变剩下数字的相对位置。
然后问题就缩减成了 \([i+1,n]\)
然后你再想想，就会发现这玩应好像冒泡排序。
具体而言，每次需要填位置 \(i\)，那么就从小到大（\(1\to i-1\)）的交换满足 \(a_j>a_i\) 的 \(j\)。
但是但是，冒泡排序要求交换的是相邻的两个元素，怎么样才能交换不相邻的两个数呢？
然后发现有个神奇的东西叫做逆排列（设排列 \(p\)，那么他的逆排列 \(q\) 需要满足 \(q_{p_i}=i\)）
发现，如果 \((i,j)\) 在排列 \(p\) 中是逆序对，那么有 \(i<j,p_i>p_j\)，而显然 \(q_{p_i}<q_{p_j},p_i>p_j\)，也就是说，\((p_i,p_j)\) 在排列 \(q\) 中是逆序对（充要条件）。从小到大交换仍然满足刚刚的策略。
然后对着 \(q\) 冒泡排序即可，构造的话直接记录下来 \(q\) 的交换历程即可。
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e3 + 10;
int b[maxn], n;
struct node{
int num, id, nid;
node(int num = 0,int id = 0,int nid = 0):num(num),id(id),nid(nid){}
}a[maxn];
struct cmp1{bool operator () (node a,node b){return a.num != b.num ? a.num < b.num : a.id < b.id;}};
struct cmp2{bool operator () (node a,node b){return a.id < b.id;}};
vector<pair<int,int> > ans;
signed main(){
n = read();
for(int i = 1;i <= n;i++){a[i] = node(read(),i);}
sort(a + 1,a + 1 + n,cmp1());
for(int i = 1;i <= n;i++)a[i].nid = i;
sort(a + 1,a + 1 + n,cmp2());
for(int i = 1;i <= n;i++)b[a[i].nid] = i;
// for(int i = 1;i <= n;i++)printf("%d ",b[i]);puts("");
for(int i = 1;i <= n;i++){
for(int j = 1;j < n;j++){
if(b[j] > b[j + 1]){
swap(b[j],b[j + 1]);
ans.push_back(make_pair(b[j],b[j + 1]));
}
}
}
printf("%d\n",ans.size());
for(auto i : ans)printf("%d %d\n",i.first,i.second);
return 0;
}