借鉴别人的思路： http://blog.csdn.net/AllenLSY/archive/2010/09/14/5884413.aspx
我是树状数组+二分实现的
#include<iostream> using namespace std; #define maxn 200005 int value[maxn],pos[maxn],result[maxn],c[maxn]; bool test[maxn]; int low(int k) { return k&(-k); } void update(int k,int n) { while(k<=n) { c[k]++; k+=low(k); } return ; } int query(int k) { int sum=0; while(k>0) { sum+=c[k]; k-=low(k); } return sum; } int binsearch(int l,int r,int t) { int left=l,right=r,mid; while(left<=right) { mid=(left+right)/2; if(mid-query(mid)==t&&!test[mid]) { test[mid]=1; break; } else if(mid-query(mid)==t&&test[mid]) right=mid-1; else if(mid-query(mid)<t) left=mid+1; else right=mid-1; } return mid; } int main() { int n,i; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) scanf("%d%d",pos+i,value+i); memset(c,0,sizeof(c)); memset(test,0,sizeof(test)); for(i=n;i>0;i--) { int t=binsearch(1,n,pos[i]+1); result[t]=value[i]; update(t,n); } for(i=1;i<=n;i++) { if(i>1) printf(" "); printf("%d",result[i]); } printf("/n"); } return 0; }
