CF1375E Inversion SwapSort[题解]

Booksnow · 2021-02-19 20:55:43 · 题解

构造

题目大意

给定长度为 n 的数列 a_1,a_2,……a_n ，找到其所有逆序对的一个排列 (u_i,v_i) ，使得依次交换 u_1 和 v_1 位置上的数、 u_2 和 v_2 位置上的数、 …… 最后得到的数列不减。

分析

经过一定的思考我们能够发现，本题的过程类似于冒泡排序的过程，最后的目的是将其变成一个单调不减数列。

那么，我们如何使用冒泡排序将其解决呢？

我们发现，冒泡排序的每一次操作是交换两个相邻位置的值，很明显本题可以交换的数有可能是非相邻的，所以我们需要对原数列进行一定的操作。

如何操作才能使：

交换两个位置上的数 \iff 交换相邻的两个值

我们发现，一个排列的逆排列是可以做到的。

因为对于一个长度为 n 排列 a[i] (满足 a[i]\in[1,n] 且没有重复元素)，他的逆排列的定义是 b[a[i]]=i，深入解读他的意思其实是 a[i] 在原排列中处于的位置，且我们发现若两个元素组成一组逆序对，在他的逆排列中他们值的大小依然相反，所以我们发现：

原问题 \iff 通过冒泡排序将 b[i] 排序为 1,2,3,4,……,n

至于交换路径我们只需要把我们交换的值记录下来就可以了。

CODE

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,Time=1e6;
struct node{ int val,num,New; }a[N];
int n;
int b[N];
int tot,ansl[Time],ansr[Time];
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline bool cmp1(node x,node y)
{
    if(x.val==y.val) return x.num<y.num;
    else return x.val<y.val;
}
inline bool cmp2(node x,node y) { return x.num<y.num; }
inline void initial() //离散化 
{
    sort(a+1,a+n+1,cmp1);
    for(register int i=1;i<=n;i++) a[i].New=i;
    sort(a+1,a+n+1,cmp2);
}
int main()
{
    n=read();
    for(register int i=1;i<=n;i++) a[i].val=read(),a[i].num=i;
    initial(); //离散化预处理 
    for(register int i=1;i<=n;i++) b[a[i].New]=i;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n-i;j++){
            if(b[j]>b[j+1]){
                int temp=b[j];
                b[j]=b[j+1],b[j+1]=temp;
                ansl[++tot]=b[j],ansr[tot]=b[j+1];
            }
        }
    }
    printf("%d\n",tot);
    for(register int i=1;i<=tot;i++) printf("%d %d\n",ansl[i],ansr[i]);
    return 0;
}