完美的石头 题解

题目大意

$n$ 个格子，第 $i$ 格有 $a_i$ 个宝石；$m$ 个 Bob，第 $i$ 个只能拿最前面 $l_i$ 个格子或最后面 $r_i$ 个格子中的宝石（$l_i+r_i<n$）。求最多能让几个 Bob 拿到宝石。

算法思路

两阶段贪心。把每个 Bob 的"右侧限制"转为 $r_i'=n-r_i+1$（即它只能拿 $[r_i',n]$）。

1. 尽量在左侧分配：把 Bob 按 $l_i$ 升序排序，用一个指针从左往右取还有宝石的格子，尽量满足每个 Bob（让它拿最靠左的可用格子）。若当前 Bob 在左侧拿不到，则把它"换"到右侧：用一个优先队列维护已分配 Bob 的右侧限制，保证被换到右侧的人右端点尽量小（这样右侧压力最小）。
2. 右侧贪心：把最终需要在右侧拿的 Bob 按右端点从大到小排序，从右往左取宝石满足它们。

正确性基于交换论证：左侧尽量多匹配、且让"必须去右侧"的人右端点尽量小，不会使答案变差。

复杂度

$O(n+m\log m)$。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<pair<int, int>> q(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> q[i].first >> q[i].second;
        q[i].second = n - q[i].second + 1;
    }
    sort(q.begin() + 1, q.end());

    int ans = 0, top = 0;
    priority_queue<int> pq;  // 存 -r，取最小 r
    vector<int> b(m + 1);
    int ptr = 1;
    for (int i = 1; i <= m; ++i) {
        while (ptr <= q[i].first && a[ptr] == 0) ++ptr;
        if (ptr <= q[i].first) {
            --a[ptr];
            ++ans;
            pq.push(-q[i].second);
        } else if (!pq.empty()) {
            pq.push(-q[i].second);
            b[++top] = -pq.top();
            pq.pop();
        } else {
            b[++top] = q[i].second;
        }
    }
    sort(b.begin() + 1, b.begin() + top + 1);
    int ptr2 = n;
    for (int i = top; i >= 1; --i) {
        while (ptr2 >= b[i] && a[ptr2] == 0) --ptr2;
        if (ptr2 >= b[i]) {
            --a[ptr2];
            ++ans;
        }
    }
    cout << ans << '\n';
    return 0;
}