Day 4 讲义：反悔贪心、优先队列与排序贡献

普通贪心要求“当前选择永远正确”。反悔贪心允许先选择，等约束被破坏时，再撤销最不划算的一次选择。

先做 -> 检查约束 -> 违约时撤销最差选择

堆的作用是：在 O(log n) 时间找到“最该撤销的对象”。

1. 优先队列速查

priority_queue<long long> mx; // 大根堆：top() 最大
priority_queue<long long, vector<long long>, greater<long long>> mn; // 小根堆：top() 最小

常用操作只有：

pq.push(x);
pq.top();
pq.pop();
pq.empty();
pq.size();

堆适合的问题特征：每一步只关心当前最小值或最大值，不需要遍历所有元素。

2. CF1526C1 / CF1526C2：反悔贪心的标准模板

从左到右遇到药水，可以喝或跳过；生命值始终不能为负，求最多喝多少瓶。

2.1 为什么“先喝再说”是安全的

先把当前药水喝下并放进小根堆。

• 若生命值非负，当前选择没有问题；
• 若生命值变负，必须少喝一瓶；
• 为了让以后最容易继续喝，应该吐掉已喝药水中数值最小的一瓶。

吐掉最小药水后，保留的瓶数与吐别的瓶相同，但剩余生命值最高。因此它不会让后续选择变差。

2.2 手动模拟

药水：4 -4 1 -3 1 -3

最终喝 5 瓶。

2.3 参考代码

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    priority_queue<long long, vector<long long>, greater<long long>> chosen;
    long long hp = 0;

    for(int i = 1; i <= n; i++){
        long long x;
        cin >> x;
        hp += x;
        chosen.push(x);

        if(hp < 0){
            hp -= chosen.top(); // 减去负数，生命值回升
            chosen.pop();
        }
    }

    cout << chosen.size() << '\n';
    return 0;
}

复杂度： O(n log n)。

2.4 C1 与 C2

CF1526C1 的 n <= 2000，很多较慢做法也许能通过；CF1526C2 的 n <= 2e5，必须使用 O(n log n)。

同一个模型在数据范围变大时，往往从“可选优化”变成“唯一正解”。

3. 1140C：枚举一维，堆维护另一维

选至多 k 首歌，得分：

时长和 × 选中歌曲美观度的最小值

按美观度从大到小扫描。扫描到一首美观度为 b 的歌时，把它当成选中集合的最小美观度：

此前见过的歌美观度都 >= b；
此时只需从这些歌里选时长最大的至多 k 首。

维护一个小根堆：

新歌时长入堆；
堆大小超过 k，弹出最短时长；
当前时长和 × b 更新答案。

这类目标的识别方法：

“某个和” × “某个最小值”
-> 枚举最小值；其余元素用数据结构维护最优和。

4. 960B：每次处理最大误差

两数组同位置差的绝对值为 d[i]。一次操作只能让某个差值加一或减一。要使平方和最小，就应该优先减少最大的 d[i]。

原因：若 x >= y，把一次减法给 x 的收益：

x^2 - (x-1)^2 = 2x-1

不小于给 y 的收益 2y-1。

所以每次从大根堆取最大差值减一再放回。若所有差为 0 而操作仍有剩余，答案会在 0 和 1 之间来回，取决于剩余操作奇偶性。

5. 845C：资源复用看最早结束时间

要把区间分给两台电视，区间不重叠才能放进同一台。

从左端点排序后，维护两台电视各自最后一个区间的结束时间：

当前区间能放到结束更早的电视吗？
能：更新结束时间。
不能：再看另一台。
都不能：NO。

更一般地，若有很多资源，用小根堆维护所有资源的最早结束时间。

这是区间贪心的核心问题：下一段最先能接到哪个资源上？

6. 1490E：排序后判断“能否继续吃下去”

把实力从小到大排序，设前缀和为：

pre[i] = 前 i 个实力之和

若 pre[i] >= a[i+1]，则已经选中的所有人合起来能战胜下一个人，之后可继续把他加入。

从大到小找最后一个“断点”：

pre[i] < a[i+1]

断点右侧的人都能成为最终胜者；左侧的人无论如何都无法跨过这个断点。

常见套路：

先排序；
前缀和表示已拥有资源；
用一个不等式判断能否进入下一阶段。

7. 易错点

8. 今日总结

选择先做，约束坏了，再撤销最差。
堆顶就是当前最该动的元素。
积乘最小值：排序枚举最小值，堆维护另一维。
区间分资源：优先看最早结束。
排序加前缀和：判断资源能否跨过下一关。