Posted on 2010-01-30 03:07
Uriel 阅读(627)
评论(0) 编辑 收藏 引用 所属分类:
POJ
跟着队长切的题，以为可以迅速的水过去。。谁知看完晕乎晕乎的，题意都不懂。。一翻Discuss说是逆序数，完全没想法。。想来想去怎么套上逆序数的东西。。基本上已经是凑答案了。。
WA了几次之后终于猜对题意了。。
由于不一定编号要排好，只要最后对应就行，所以第一步就是改编号，其中一个改为按顺序的1-N，另一个改为与之对应的编号，求其逆序数即可，我的丑陋代码。求逆序数用mergeSort，以前做2299写的，做模板用了~
/**//*Problem: 2188 User: Uriel
Memory: 180K Time: 16MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int b[1010],N,change,a[1010],flag[1010],c[1010];
void merge(int p,int q,int r)
{
int i,j=0;
int beginA=p,endA=q,beginB=q+1,endB=r;
while(beginA<=endA && beginB<=endB)
{
if(a[beginA]<=a[beginB])
{
b[j++]=a[beginA++];
}
else
{
b[j++]=a[beginB++];
change += q - beginA + 1;
}
}
while(beginA<=endA)
{
b[j++]=a[beginA++];
}
while(beginB<=endB)
{
b[j++]=a[beginB++];
}
for(i=0;i<j;i++)
{
a[p+i]=b[i];
}
}
void mergeSort(int first, int last)
{
int mid;
if(first<last)
{
mid=(first+last)/2;
mergeSort(first,mid);
mergeSort(mid+1,last);
merge(first,mid,last);
}
}
int main()
{
int i,x,y;
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d %d",&a[i],&c[i]);
flag[c[i]]=i;
}
for(i=0;i<N;i++)
{
a[i]=flag[a[i]];
}
change=0;
mergeSort(0,N-1);
printf("%d\n",change);
system("PAUSE");
return 0;
}