[ARC180B] Improve Inversions

Atcoder传送门 $an d$ 洛谷传送门

题目大意

给出一个数列 $P$ 和一个整数 $K$ ,然后重复做以下操作（直到不能做为止）：选择整数 $l$ 和 $r$ $\leq l < r \leq N )$ 然后交换 $P_l$ 和 $P_r$ 的值。其中，这对 $(l, r)$ 必须同时满足以下条件:

这对 $(l, r)$ 以前从未被选过
$P_l\ > P_r$
$ K\ \leq\ r-l $

求最多能操作多少次，并给出相应方案。

分析

这道题可以稍微贪一下。既然想操作数最大，那么，就要尽可能在每一次交换后，让 $P_l$ 大一点。综合一下，我们可以构成图来实现此题。步骤如下：

给每个点与其 $K$ 个后的点在大于它的情况下连单向边（这道题尽可能直接存对应点，因为后面要排序）。
存下有出度的点，然后按权值从小到大排序。
循环排完序的点，用某个数组记录其连边的点。
对那个上一步所描述的数组排一下序（从大到小）。
输出（先输出循环的点，再输出被连边的点），并交换两点的权值。

小提示：不要直接将两点排序，即改变其原顺序。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=710;
int n,k,p[N],ans,eg[N][N],cnt[N],sat[N],cont,bz[N];
void qsort(int l,int r){
	int i=l,j=r,mid=p[sat[(l+r)/2+1]];
	while(i<=j){
		while(p[sat[i]]<mid) i++;
		while(p[sat[j]]>mid) j--;
		if(i<=j){
			swap(sat[i],sat[j]);
			i++,j--;
		}
	}
	if(l<j) qsort(l,j);
	if(i<r) qsort(i,r);
}
void qsort2(int l,int r){
	int i=l,j=r,mid=p[bz[(l+r)/2+1]];
	while(i<=j){
		while(p[bz[i]]>mid) i++;
		while(p[bz[j]]<mid) j--;
		if(i<=j){
			swap(bz[i],bz[j]);
			i++,j--;
		}
	}
	if(l<j) qsort2(l,j);
	if(i<r) qsort2(i,r);
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+k;j<=n;j++){
			if(p[j]<p[i]){
				eg[i][++cnt[i]]=j;
				ans++;
			}
		}
	}
	printf("%d\n",ans);
	if(ans==0) return 0; 
	for(int i=1;i<=n;i++){
		if(cnt[i]){
			sat[++cont]=i;
		}
	}
	qsort(1,cont);
	for(int i=1;i<=cont;i++){
		memset(bz,0,sizeof(bz));
		for(int j=1;j<=cnt[sat[i]];j++){
			bz[j]=eg[sat[i]][j];
		}
		qsort2(1,cnt[sat[i]]);
		for(int j=1;j<=cnt[sat[i]];j++){
			printf("%d %d\n",sat[i],bz[j]);
			swap(p[bz[j]],p[sat[i]]);
		}
	}
	return 0;
}