CF1375E Inversion SwapSort

一、题目

点此看题

二、解法

这种求解之类的问题可以考虑构造，其中有一种常用方法就是缩减问题规模。

先考虑对于一个排列的求解，其他情况可以通过双关键字（值，下标）转化成排列。我们把 $n$放在位置 $n$，而且要保证这个操作用完了和位置 $n$相关的逆序对，并且前面的相对顺序不变（以前存在逆序对还是存在，不存在还是不存在）

设 $p[i]$为 $i$值的位置， $a[i]$为 $i$位置的值，构造出一种方法为依次交换 $(p[a[i]+1],n)....(p[n],n)$，可以自行检查一下上面的条件。

#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 1005;
int read()
{int num=0,flag=1;char c;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar();return num*flag;
}
int n,m,k,a[M],p[M],x[M*M],y[M*M];
struct node
{int a,b;bool operator < (const node &r) const{if(a==r.a) return b<r.b;return a<r.a;}
}s[M];
signed main()
{n=read();for(int i=1;i<=n;i++){s[i].a=read();s[i].b=i;}sort(s+1,s+1+n);for(int i=1;i<=n;i++){a[s[i].b]=i;p[i]=s[i].b;}for(int i=n;i>=1;i--){for(int j=a[i]+1;j<=i;j++)x[++k]=p[j],y[k]=i;for(int j=a[i];j<i;j++){p[j]=p[j+1];a[p[j]]=j;}}printf("%d\n",k);for(int i=1;i<=k;i++)printf("%d %d\n",x[i],y[i]);
}