题解：P11453 [USACO24DEC] Deforestation S

· · 题解

题目分析

这道题似乎就是 CSP-S T2 的加强版

根据 CSP-S T2 得出的经验，我们可以贪心地从左往右删，因为如果在这个位置删满足条件，那么在右边删可能会浪费条件导致不优，但一定不会因为改到右边而多删。

那么这样我们就可以非常简单的写出一个 O(nk) 的暴力贪心了。接下来我们只需要考虑如何将这个算法优化即可。

这里阐述官方题解的优化方法，即用优先队列进行优化，具体实现比较巧妙。

我们将限制按左端点从小到大排序，树按坐标从小到大排序，并将这两个排序后的结果合并起来记为 events。

然后我们开一个优先队列 Q，它的第一位是最多能砍多少棵树，第二位是目前处理到的右端点坐标。它以第二位为第一关键字，第一位为第二关键字的小根堆。

我们扫一遍 events：

若这是一个限制，则我们按照贪心策略尝试将这个限制中所有能砍的树全砍了，即 Q.emplace(answer + p, r);。

若这是一棵树，我们先把所有没有管辖这棵树的限制全都从 Q 中弹出，由于我们已经将 events 排序，所有左端点一定合法，我们只需要判断右端点是否合法即可。

若 Q 中无元素，说明无限制管辖这棵树，自然可以砍掉它，令答案自增；或者若“目前最多砍的树的数量比目前答案要大（Q.top().first > answer）”，说明这个限制中的树我们还没有砍完，那我们也可以砍掉这棵树。

代码

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

const int Maxn = 5e5 + 5;
int t, n, k, l, r, p;
int trees[Maxn];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    for (cin >> t; t--; ) {
        cin >> n >> k;
        for (int i = 0; i < n; i++)
            cin >> trees[i];
        sort(trees, trees + n);
        vector<tuple<int, int, int, int>> events;
        // 第一位是（限制：左端点 / 树：坐标），第二位表示类型（0：限制 / 1：树）。
        // 第三位是（限制：右端点 / 树：无意义），第四位是（限制：这个区间内还能砍多少棵树 / 树：无意义）。
        // 特别注意第二位的类型不能调换顺序，因为我们要先处理限制再处理树。
        for (int i = 0; i < n; i++)
            events.emplace_back(trees[i], 1, 0, 0);
        while (k--) {
            cin >> l >> r >> p;
            events.emplace_back(l, 0, r, upper_bound(trees, trees + n, r) - lower_bound(trees, trees + n, l) - p /* 计算区间内还能砍多少棵树。 */);
        }
        sort(events.begin(), events.end());
        // 将所有东西按照左端点从小到大排序。
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
        // 第一位是最多能砍多少棵树，第二位是目前处理到的右端点坐标。
        // 以第二位为第一关键字，第一位为第二关键字的小根堆。
        int answer = 0;
        for (const auto& event : events) {
            tie(l, k, r, p) = event;
            if (k == 0) {
                Q.emplace(answer + p, r);
                // 将这个限制所对应的区间内的树全都砍掉，并更新右端点。
            } else {
                for (; !Q.empty() && Q.top().second < l; Q.pop());
                // 将未包含这棵树的限制全都清除掉。
                answer += Q.empty() // 没有限制可以管辖这棵树，当然可以砍掉。
                          || Q.top().first > answer; // 这个限制还没有砍完，根据贪心策略我们能砍就砍。
            }
        }
        cout << answer << '\n';
    }
    return 0;
}