题解：P10688 Buy Tickets

· · 题解

前置知识

思路

如果按照正常顺序从前向后模拟，问题会变得很复杂。但是反过来，我们从最后一个人开始从后向前模拟，整个问题就会变得非常简单。

为什么呢？考虑一个简单的例子：首先来了一个人，站在第 1 个人后面。接着又来了若干个人，都没有素质插在第 1 个人的后面。最后一个人来了，他也没有素质插在了第 1 个人后面。诶，此时，最后一个人就是第 1 个人后面的第一个人。

发现了什么？最后一个插队的人是离他所排的人最近的，而第一个插队的人是离他所排的人最远的。

所以，从后往前模拟，就可以顺利解决此题。扫描每一个人，若他排在第 x 个人后面，那么查找队伍中哪一个位置前面有 x 个空位，然后把这个人放在这里。

如何快速获取从队头到某一处之间有多少个空位？使用树状数组，维护每一个位置上有没有人（有人为 0，没人为 1）。利用树状数组能快速求出区间和的性质，即可求出从队头到某一处之间有多少个空位。那如何查找到这个位置？很自然地可以想到二分查找。

至此，问题解决。

代码

#include<bits/stdc++.h>
using namespace std;

int n;
int a[200010],v[200010];
int ans[200010];

int c[200010];

void Add(int x,int y){
    for(;x<=n;x+=x&-x) c[x]+=y;
}

int Query(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(cin>>n){
        for(int i=1;i<=n;++i) c[i]=0;
        for(int i=1;i<=n;++i) Add(i,1);
        for(int i=1;i<=n;++i) cin>>a[i]>>v[i];
        for(int i=n;i>=1;--i){
            int l=1,r=n;
            while(l<r){
                int mid=(l+r)>>1;
                if(Query(mid)>=a[i]+1) r=mid;
                else l=mid+1;
            }
            ans[l]=v[i];
            Add(l,-1);
        }
        for(int i=1;i<=n;++i) cout<<ans[i]<<" ";
        cout<<"\n";
    }

    return 0;
}