Posted on 2010-01-30 03:07
Uriel 閱讀(633)
評論(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;
}