Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 2188 Cow Laundry---求逆序数

Posted on 2010-01-30 03:07 Uriel 阅读(626) 评论(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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理