题解：P10688 Buy Tickets

myxRUC · 2025-08-11 16:10:41 · 题解

转化利用树状数组！！！

由于是排队问题，所以后进入队列的人拥有站在哪里的决定权，因此我们倒序处理进入队列的人。

因此每个人进入队列的时候，如果他的理想位置是 x 的话,他显然没有任意挑选位置的自主权，必须在剩下的位置里面挑选一个最满意的。

由此可知我们整道题所要做的就是维护一个数组，来存储第 k 个点以前剩余的座位个数，比如 find(5)=4，就说明前五个座位里面还剩下四个，那么如果此时进入队列的人想坐在第四个位置，就要看 find(4) 是不是等于 4，如果是，就要坐在第四个位置；否则，说明第五个位置没人坐，就坐在第五个位置。这也就是二分的思想。

int l = 1, r = n;
while (l < r) {
    int mid = (l + r) / 2;
    int t = find(mid);
    if (t < p[i]) {
        l = mid + 1;
    }
    else {
        r = mid;
    }
}

显然 find(i) 有前缀和的思想，而又要进行单点修改，所以就要借助树状数组。

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int v, int x) {//单点修改
    for (int i = x; i <= n; i += lowbit(i)) {
        a[i] += v;
    }
}

inline int find(int x) {//求前缀和
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ans += a[i];
    }
    return ans;
}

因此在第 i 座位被占用以后，使用 add(-1,i) 这个操作就行了，这样就很高效的完成树状数组的维护。

完整代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 200005;

int a[N], num[N], c[N], p[N];
int cnt, n;

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int v, int x) {
    for (int i = x; i <= n; i += lowbit(i)) {
        a[i] += v;
    }
}

inline int find(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ans += a[i];
    }
    return ans;
}

int main(void) {
    while (cin >> n) {

        memset(a, 0, sizeof a);
        memset(c, 0, sizeof c);

        for (int i = 1; i <= n; i++) {
            cin >> p[i] >> num[i];
            p[i]++;
            add(1, i);
        }

        for (int i = n; i >= 1; i--) {
            int l = 1, r = n;
            while (l < r) {
                int mid = (l + r) / 2;
                int t = find(mid);
                if (t < p[i]) {
                    l = mid + 1;
                }
                else {
                    r = mid;
                }
            }
            c[r] = num[i];
            add(-1, r);
        }

        for (int i = 1; i <= n; i++) {
            cout << c[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}