題意：排隊(duì)買(mǎi)票，但是 中途 出現(xiàn)插隊(duì)情況，比如 0 123，代表值為123的人 插入到 0 的位置，如果后面 出現(xiàn) 0 456，那么新的 0的位置就是 456，123就變成是 1的位置了

分析：這道題應(yīng)該從后往前插入，當(dāng)要插的位置小于左邊的空位數(shù)時(shí)，就往左邊插，否則往右邊插，并且此刻插的位置要減去左邊的空位數(shù)

#include<cstdio> #include<iostream> #define lson l,m,now*2 #define rson m+1,r,now*2+1 #define M 200010 using namespace std; int sum[M*4],ans[M]; struct node {int pos,zh; };node per[M]; void push_up(int now) {sum[now]=sum[now*2]+sum[now*2+1]; } void build(int l,int r,int now) {if(l==r){sum[now]=1;return;}int m=(l+r)/2;build(lson);build(rson);push_up(now); } void change(int p,int v,int l,int r,int now) {if(l==r){ans[l]=v;sum[now]=0;return;}int m=(l+r)/2;if(p<sum[now*2]) change(p,v,lson);else change(p-sum[now*2],v,rson);push_up(now); } int main() {int n;while(~scanf("%d",&n)){build(0,n-1,1);for(int i=0;i<n;i++)scanf("%d%d",&per[i].pos,&per[i].zh);for(int i=n-1;i>=0;i--)change(per[i].pos,per[i].zh,0,n-1,1);for(int i=0;i<n;i++)printf("%d ",ans[i]);printf("\n");}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/harden/p/5624824.html

總結(jié)

以上是生活随笔為你收集整理的Buy Tickets(poj 2828)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。