這題開始的思路就是模擬：就像數組中插點一樣，每一個想買票的人都想往前插隊！ 但是這樣的話肯定TLE， 看了別人的思路之后才恍然大悟！ 正解：將開始的正序插入，變成倒序插入，這樣的話，想一想：第 i 個人想要插在 p[i]的位置上，那么就要保證所插入的位置之前一定要有 p[i]-1個空位！因為一定會有p[j]<p[i]（0<=p[j]<=j,每個人都想往前插隊） 的第j個人插在p[i]的位置的前邊！ 如果i<j; && p[i]==p[j], 倒序插入中，第j個人先插入， 那么第i個人在保證插入的位置之前有p[i]-1個空位的同時，又要插入到第 j 個人的后邊！
?
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define M 200005 6 using namespace std; 7 8 pair<int, int>per[M]; 9 int ret[M]; 10 int tree[M*4]; 11 int n; 12 13 void buildT(int p, int ld, int rd){ 14 if(ld==rd){ 15 tree[p]=1; 16 return ; 17 } 18 int mid=(ld+rd)>>1; 19 buildT(p<<1, ld, mid); 20 buildT(p<<1|1, mid+1, rd); 21 tree[p]=tree[p<<1]+tree[p<<1|1]; 22 } 23 24 void updateT(int p, int ld, int rd, int pos, int val){ 25 if(ld==rd){ 26 tree[p]=0; 27 ret[ld]=val; 28 return ; 29 } 30 int mid=(ld+rd)>>1; 31 if(tree[p<<1]>pos) 32 updateT(p<<1, ld, mid, pos, val); 33 else 34 updateT(p<<1|1, mid+1, rd, pos-tree[p<<1], val); 35 36 tree[p]=tree[p<<1]+tree[p<<1|1]; 37 } 38 39 int main(){ 40 int i; 41 while(scanf("%d", &n)!=EOF){ 42 buildT(1, 1, n); 43 for(i=1; i<=n; ++i) 44 scanf("%d%d", &per[i].first, &per[i].second); 45 for(i=n; i>=1; --i) 46 updateT(1, 1, n, per[i].first, per[i].second); 47 48 printf("%d", ret[1]); 49 for(i=2; i<=n; ++i) 50 printf(" %d", ret[i]); 51 printf("\n"); 52 } 53 return 0; 54 }
?
1 //樹狀數組～～不解釋 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<algorithm> 6 7 #define N 200005 8 using namespace std; 9 10 int tree[N]; 11 int pos[N], val[N]; 12 int ret[N]; 13 int n; 14 15 int lowbit(int x){ 16 return x&(-x); 17 } 18 19 void buildT(){ 20 for(int i=1; i<=n; ++i){ 21 tree[i]=0; 22 for(int j=i-lowbit(i)+1; j<=i; ++j) 23 tree[i]+=1; 24 } 25 } 26 27 void updateT(int x){ 28 while(x<=n){ 29 tree[x]-=1; 30 x+=lowbit(x); 31 } 32 } 33 34 int getSum(int x){ 35 int s=0; 36 while(x>0){ 37 s+=tree[x]; 38 x-=lowbit(x); 39 } 40 return s; 41 } 42 43 int main(){ 44 while(scanf("%d", &n)!=EOF){ 45 buildT(); 46 for(int i=1; i<=n; ++i){ 47 scanf("%d%d", &pos[i], &val[i]); 48 ret[i]=-1; 49 } 50 for(int i=n; i>=1; --i){ 51 int ld=1, rd=n; 52 bool flag=false; 53 while(ld<=rd){ 54 int mid=(ld+rd)>>1; 55 int s=getSum(mid); 56 //如果當前的位置沒有人插入并且該位置的之前的人數恰好為pos[i] 57 if(ret[mid]==-1 && s==pos[i]+1){ 58 updateT(mid); 59 ret[mid]=val[i]; 60 flag=true;//已經找到不用在繼續尋找了 61 break; 62 } 63 else if(s>=pos[i]+1) 64 rd=mid-1; 65 else ld=mid+1; 66 } 67 if(!flag) ret[rd+1]=val[i];//直到找到當前的位置沒有人插入并且該位置的之前的人數恰好為pos[i] 68 } 69 printf("%d", ret[1]); 70 for(int i=2; i<=n; ++i) 71 printf(" %d", ret[i]); 72 printf("\n"); 73 } 74 return 0; 75 }
?
