Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

poj 4020 逆序对

来源: lencle 分享至:

问了jx,才看懂了题意。

 给定100000个二元组(x,y),找到一个排列,使得这个排列下x的逆序对数和y的逆序对数之和最小
只要是相同颜色的就算一个  (1,2) (2,1) 这种情况算一个。 不知道我说没说清楚,嘴笨= =
#include <iostream>
#include <algorithm>
using namespace std;
struct data {
       int a,b;
}a[100010];
int t[100010],n;
__int64 ans;
bool cmp(data a,data b) {
     if (a.a<b.a) return true;
     else if (a.a==b.a && a.b<b.b) return true;
     return false;
}
void digui(int l,int r) {
     if (l==r) return;
     int mid = (l+r)>>1;
     digui(l,mid);
     digui(mid+1,r);
     int i=l,j=mid+1,k=l,p;
     while (i<=mid && j<=r) {
           if (a[i].b>a[j].b) {
                          ans+=mid-i+1;
                          t[k] = a[j].b;
                          j++;
           }
           else {
                t[k] = a[i].b;
                i++;
           }
           k++;
     }
     if (i==mid+1) for (p=j;p<=r;p++) t[k++] = a[p].b;
     else for (p=i;p<=mid;p++) t[k++] = a[p].b;
     for (k=l;k<=r;k++) a[k].b = t[k];
}
int main() {
    while (~scanf("%d",&n)) {
          for (int i=1;i<=n;i++)
              scanf("%d%d",&a[i].a,&a[i].b);
          sort(a+1,a+n+1,cmp);
          ans=0;
          digui(1,n);
          printf("%I64d\n",ans);
    }
    return 0;
} 




Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史