问了jx,才看懂了题意。
给定100000个二元组(x,y),找到一个排列,使得这个排列下x的逆序对数和y的逆序对数之和最小#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; }