CF #324 DIV2 E题

这题很简单，把目标位置排序，把目标位置在当前位置前面的往前交换，每次都是贪心选择第一个满足这样要求的数字。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

const int MAX=2005;

int p1[MAX],p2[MAX],mp[MAX];

int pos[MAX],goal[MAX];

bool rip[MAX];

vector<pair<int,int> >ans;

int main(){

	int n,counts,ans_counts,cost;

	while(scanf("%d",&n)!=EOF){

		counts=0;

		ans.clear();

		cost=0;

		for(int i=1;i<=n;i++) scanf("%d",&p1[i]);

		for(int i=1;i<=n;i++){

			scanf("%d",&p2[i]);

			mp[p2[i]]=i;

		}

		for(int i=1;i<=n;i++){

			if(p1[i]!=p2[i]){

				pos[++counts]=i;

				goal[counts]=mp[p1[i]];

			}

		}

/*		for(int i=1;i<=counts;i++)

			cout<<pos[i]<<" ";

		cout<<endl;

		for(int i=1;i<=counts;i++){

			cout<<goal[i]<<" ";

		}

		cout<<endl;*/

		memset(rip,false,sizeof(rip));

		if(counts==0){

			puts("0");

			puts("0");

			continue;

		}

		int lmin=1;

		for(int i=1;i<=counts;i++){

			if(goal[i]<pos[i]){

				int rmax=i-1,last=i,g=goal[i];

				while(pos[last]!=g){

					if(!rip[rmax]){

						ans.push_back(make_pair(pos[last],pos[rmax]));

						swap(goal[last],goal[rmax]);

						if(goal[last]==pos[last]) rip[last]=true;

						cost+=abs(pos[last]-pos[rmax]);

						last=rmax;

					}

					rmax--;

				}

				rip[last]=true;

				for(;;lmin++) if(!rip[lmin]) break;

			}

		}

		printf("%d\n",cost);

		printf("%d\n",ans.size());

		int sz=ans.size();

		for(int i=0;i<sz;i++){

			printf("%d %d\n",ans[i].first,ans[i].second);

		}

	}

	return 0;

}