题解：P14097 [POCamp 2022] 救火 / Brinnande träd

Neri_qwq · 2025-09-29 11:06:48 · 题解

我变强了能场切蓝了 awa。

先考虑朴素贪心。

遍历每一棵树，能救就救，救完把当前的时间加上救这棵树所需要的时间，统计答案即可。

然后发现样例 2 会出错，我们分析一下原因：

• 根据我们的贪心策略，第一棵树可以被救下，但是耗费了 5 的时间，后面的都没法救了。
• 我们不救第一棵树，发现其它都可以被救。

于是考虑反悔贪心。

• 我们使用一个大根堆 q，记录每棵救下的树所用的时间。
• 首先跟朴素贪心思路一样，把当前能救的都救下，将时间入堆。
• 然后考虑另外一种情况，目前局面下这棵树 i 无法被救下，而把已救的需要时间最长的树（堆顶） j 去掉后，i 能被救下，并且 a_i \le a_j。如果我们不救 j 而救 i，可以让总耗费时间变小，后面能救的树也更多，因此我们在总时间里把 a_j 减掉，加上 a_i。把堆顶删掉，让 a_i 入堆。

遍历复杂度 O(n)，堆复杂度 O(\log n)，时间复杂度 O(n \log n)。

这里可能有些晦涩难懂，代码中有注释，可以结合代码理解。

#include <bits/stdc++.h>
using namespace std;
int x[400005], a[400005];
int main()
{
    int n, cnt = 0, ans = 0; // cnt 表示目前的时间，ans 表示救了几棵树
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    priority_queue<int> q; // 大根堆（优先队列）
    for (int i = 1; i <= n; i++)
    {
        if (cnt <= x[i]) // 直接可以救下
        {
            q.push(a[i]); // 入队
            cnt += a[i]; // 累计总时间
            ans++; //答案 + 1
        }
        else if (!q.empty() /*堆不为空（防 RE）*/ && cnt - q.top() <= x[i] /*不救堆顶的树可以救下这棵树*/ && a[i] < q.top() /*救这棵树所要的时间比救堆顶的树所要的时间小*/) 
        {
            cnt -= q.top();
            cnt += a[i]; // 更改总时间
            q.pop();
            q.push(a[i]); // 弹出队首，加入现时间
      // 这里不用给答案 + 1
        }
    }
    cout << ans;
    return 0;
}

说句闲话，赛时输出了 cnt 硬控了我 5 min。