CF1375E Inversion SwapSort(构造&思维)题解

发布于 2021-10-30  36 次阅读


题目大意

给定一个长度为 $n$ 的序列 $a_1,\dots,a_n$,求出 $a$ 中所有逆序对位置 $(pos1_{1},pos2_1),\dots,(pos1_n,pos2_n)$ 的一个排列,使得按照这个排列依次交换位置后序列单调不降。

$1 \le n \le 10^3$,$1 \le a_i \le 10^9$。

解题思路

发现题目中要交换的是位置,而逆序对是跟着值走,而不是位置走的。

所以考虑如果交换的不是原本逆序对的位置而是交换后当前逆序对所在位置怎么做。

我们发现类似于冒泡排序的做法,我们可以每次交换相邻两个逆序对。

这样做,前面部分内部的贡献以及后面部分内部的贡献肯定不会变,我们只需要考虑当前部分内部贡献,以及当前部分与前面后面的跨区间贡献。那么显然,内部的交换减少了一个逆序对,前面部分与当前这两个数的贡献,以及和后面部分和当前这两个数的贡献是不会改变的(因为这两个数在相对于前后两个部分的位置是没有变的),那么整个序列的逆序对数就减少了 $1$。

而我们每次都这样调整,每次可以减少一个原序列中的逆序对。而这样的操作又可以进行逆序对数量次。所以最后一定可以到达一个有序状态。

然后考虑交换的是原本逆序对位置的情况,我们发现我们令 $b_{a_i}=i$,这样转化出的序列 $b_1...b_n$ 就满足交换的是跟着值走的逆序对位置。而且我们发现原本序列中的逆序对需要满足 $i<j$ 且 $a_i>a_j$,在 $b$ 序列中,我们发现这样的一对 $(i,j)$ 的关系变成了 $i>j$ (因为 $a_i>a_j$)且 $b_i<b_j$(因为 $i<j$),仍然是一对逆序对。也就是说,原序列和转化后序列的逆序对是完全不变的。

然后我们发现我们上面的讨论都是基于 $a$ 数组是一个排列的($a \to b$ 的转化需要用到这一点),而题目中给出的序列可能并不是一个排列,怎么办呢?

注意到原序列中可能出现值相同的情况,所以我们对于原序列中的一个数,值作为它的第一关键字,人为给予它一个标号作为第二关键字,再进行离散化,保证没有相同的值。离散化后再进行上面的操作就可以了。

Code

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

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
const int N=2005;

int n,p[N];
pair<int,int> a[N],b[N];
vector < pair<int,int> > ans;

int main(){
    //freopen("CF1375E.in","r",stdin);
    //freopen("CF1375E.out","w",stdout);
    n=read();
    for (int i=1;i<=n;++i) a[i]=mp(read(),i),b[i]=a[i];
    sort(b+1,b+n+1);
    for (int i=1;i<=n;++i)
        a[i].first=lower_bound(b+1,b+n+1,a[i])-b;
    // printf("a: "); for (int i=1;i<=n;++i) printf("%d ",a[i].first); printf("\n");
    for (int i=1;i<=n;++i) p[a[i].first]=i;
    // printf("p: "); for (int i=1;i<=n;++i) printf("%d ",p[i]); printf("\n");
    for (int i=1;i<=n;++i)
        for (int j=n;j>=2;--j)
            if (p[j]<p[j-1]){
                ans.push_back(mp(p[j],p[j-1]));
                swap(p[j],p[j-1]);
            }
    printf("%d\n",(signed)(ans.size()));
    for (auto it : ans)
        printf("%d %d\n",it.first,it.second);
    return 0;
}

我们无法选择过去,但我们可以改变未来。