洛谷P1966 火柴排队[NOIP提高组2013]

我确信我应该是做过这道题……就当再写一遍好了。

贪心思想，一番证明得出a和b数组中最小对最小，次小对次小……时解最优。那么先处理出a，b之间的对应关系，然后按照该关系求a或者b的逆序对数量就是答案

 /*by SilverN*/

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 const int p=;

 struct num{

     int w;

     int num;

 }a[mxn],b[mxn];

 int cmp(num x,num y){return x.w<y.w;}

 int cmp2(num x,num y){return x.num<y.num;}

 int link[mxn];

 int t[mxn];

 int n,ans;

 int lowbit(int x){

     return x&-x;

 }

 void add(int x,int v){

     while(x<=n){

         t[x]+=v;

         x+=lowbit(x);

     }

 }

 int sum(int x){

     int res=;

     while(x){

         res+=t[x];

         x-=lowbit(x);

     }

     return res;

 }

 int main(){

     scanf("%d",&n);

     int i,j;

     for(i=;i<=n;i++)scanf("%d",&a[i].w),a[i].num=i;

     for(i=;i<=n;i++)scanf("%d",&b[i].w),b[i].num=i;

     sort(a+,a+n+,cmp);

     sort(b+,b+n+,cmp);

     for(i=;i<=n;i++) link[a[i].num]=b[i].num;

     sort(a+,a+n+,cmp2);

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

         add(link[i],);

         ans=(ans+i-sum(link[i]))%p;

     }

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

     return ;

 }

秒客网

洛谷P1966 火柴排队[NOIP提高组2013]

相关文章