Day 3 讲义：贪心证明、排序与交换论证

贪心不是“感觉这样选比较好”。贪心算法每一步都做不可撤销的选择，因此必须回答：为什么存在一个最优方案，也会做出同样的选择？

今天把常见证明方式和六道题连起来。

学习方式：每次想用贪心时，先写出“我当前选了什么”“换掉它会怎样”“后面还会不会更差”。

1. 贪心正确性的三种常用证法

1.1 交换论证

设贪心第一步选了 g。如果任意最优方案没有选 g，设它选了 x。证明把 x 换成 g 后：

仍然可行；
答案不变差；

那么就得到一个同样优秀、且第一步与贪心相同的最优方案。之后对剩余部分重复即可。

这就是“选大的、选小的、先结束的、代价最小的”为什么经常成立的原因。

1.2 不变量

有些题不需要比较所有方案，只要发现操作永远不改变某个量。

例如若每次操作让一个数 +1、另一个数 -1，则总和不变：

a1 + a2 + ... + an 恒定。

不变量常用来回答“能否达到”“最终最多有几种值”“奇偶性会不会改变”。

1.3 反证与前后缀

若题目问“整个数组是否优于任何真子段”，可以把真子段拆为：

前缀或后缀。

然后只需检查最大真前缀和、最大真后缀和，而不必枚举所有子数组。

2. 135A：排序后只留下一个最大值

题目操作最终只关心：除了最大值以外的数是否能被替换成最小值。

排序后：

a[1] <= a[2] <= ... <= a[n]

输出：

1 1 ... 1 a[n]

这个题的训练点不是代码，而是先把操作的最终效果看透。遇到“可以不断替换、增加、减少”的题，先问：最后哪些量真正无法改变？

复杂度： O(n log n)。

3. 246B：先找不变量，再数答案

每次选两个不同位置，一个加一、另一个减一，总和不变。

若允许不断操作，数组中最终能出现多少种不同数，只由总和能否平均分配决定：

sum % n == 0 -> 可以全部相等，答案 1
否则         -> 只能分成相邻两种整数，答案 2

为什么只会有两种？设平均值为非整数 k + r/n，所有整数的平均值要接近它，只能由 k 和 k+1 混合组成。

这类题的关键不是模拟操作，而是把“操作很多次”压缩为一个不变量结论。

4. 1285B：最大真前缀/后缀和

题目要求整个数组的和严格大于任意非空真子数组的和。

若存在一个坏子数组，它可以分两类：

1. 不含第一个元素；
2. 不含最后一个元素。

因此只需检查：

最大前缀和（长度 < n）
最大后缀和（长度 < n）

若其中任意一个大于等于总和，则答案为 NO。

4.1 线性扫描写法

long long sum = 0, pre = 0, bestPre = -(1LL << 60);
for(int i = 1; i <= n; i++) sum += a[i];

for(int i = 1; i < n; i++){
    pre += a[i];
    bestPre = max(bestPre, pre);
}

后缀从右向左同理。

注意： 这里是“真子数组”，不能把整个数组自己拿来比较，所以循环只到 n-1。

5. 1203E：排序后占最近空位

每个拳击手原本在体重 x，可以站到 x-1、x、x+1。目标是让不同体重数量尽量多。

从小到大处理每个人。当前 x 的最佳优先级：

x-1 没占用 -> 占 x-1
否则 x 没占用 -> 占 x
否则 x+1 没占用 -> 占 x+1
否则放弃

为什么优先占小位置？因为较小位置一旦空着，后面的人不会比当前人更适合填它；而把当前人放得尽量靠左，能给后面留下更多大的位置。

5.1 参考代码

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

const int N = 200000 + 10;
int a[N];
bool used[N + 2];

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

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] > 1 && !used[a[i] - 1]){
            used[a[i] - 1] = true;
            ans++;
        }else if(!used[a[i]]){
            used[a[i]] = true;
            ans++;
        }else if(!used[a[i] + 1]){
            used[a[i] + 1] = true;
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度： 排序 O(n log n)，扫描 O(n)。

6. 1296D：把额外攻击变成代价

怪物每轮先受到你的攻击 a，活着才反击 b。若你愿意额外花一次攻击机会，就能减少需要承受的反击次数。

对每只怪物，先算它在只用普通攻击时最后一轮之前还会反击多少次。令：

r = hp % (a+b)

若 r == 0，令 r = a+b。为了在这一轮周期内击杀它，需要的额外攻击次数是：

cost = (r-1) / a

每花一个额外攻击，能多击杀一只怪物；总预算为 k。于是：

算出每只怪物的 cost；
按 cost 从小到大排序；
能买就买。

这是“收益都相同，代价不同”的标准贪心：优先选代价最小的。

7. 1760F：二分答案的入口

题目问一个最大周期 k 是否可行。此类“最大化一个整数答案”的题，先判断可行性是否单调：

k 可行 -> 更小的 k 是否一定可行？

若答案是肯定的，就可以二分。

7.1 标准框架

int l = 0, r = 200000, ans = -1;
while(l <= r){
    int mid = (l + r) >> 1;
    if(check(mid)){
        ans = mid;
        l = mid + 1;
    }else{
        r = mid - 1;
    }
}

本题中先把奖励从大到小排序。固定周期后，前一段奖励会循环出现，check(k) 用前缀和在 O(n) 或 O(1) 内算出最多收益。

二分答案的真正难点永远是 check(mid)：

mid 表示什么？
固定 mid 后，如何快速判断？
为什么可行性单调？

8. 今日易错点与训练建议

建议顺序：135A -> 246B -> 1285B -> 1203E -> 1296D -> 1760F。

9. 今日口诀

贪心先问凭什么，交换不差才敢选。
操作不变找总和，复杂过程压成结论。
位置冲突先排序，优先占最左空位。
收益相同选最便宜，答案单调就二分。