🧠 贪心算法专题 · 课堂笔记

一、多服务台调度 —— 排队打水问题

题目特征

• 有 $m$ 个水龙头，$n$ 个人排队打水，每人打水耗时 $a_i$。
• 一个水龙头同一时间只能服务一个人，求 最小总完成时间（最后一个人打完水的时间）。

贪心策略

• 对于每一个新来的人，总是选择 当前累计时间最少 的水龙头。
• 即维护数组 $t[1..m]$ 表示每个水龙头的总耗时，每次在 $t$ 中找最小值，把当前人加进去。

核心代码框架

int t[10010] = {0};        // t[j]：第 j 个水龙头当前总用时
for (int i = 1; i <= n; i++) {
    int mi = 1e18, mii;   // 找最小值及其位置
    for (int j = 1; j <= m; j++) {
        if (t[j] < mi) {
            mi = t[j];
            mii = j;
        }
    }
    t[mii] += a[i];        // 安排到耗时最少的水龙头
}
ans = max(t[1..m]);        // 最终答案

二、物品仅有两种重量的背包贪心 —— 吃鱼问题

题目特征

• 有 $n$ 条鱼，每条鱼有重量 $w$（只有 $1$ 或 $2$）和价值 $v$。
• 背包总承重为 $m$，问 最大总价值。

贪心策略

1. 把重量为 $1$ 的鱼和重量为 $2$ 的鱼分开，各自按 价值从大到小 排序。
2. 分别求前缀和 $s1[i]$（吃 $i$ 条重 $1$ 的鱼的最大价值）和 $s2[j]$。
3. 枚举吃 $i$ 条重 $1$ 的鱼，剩余容量给重 $2$ 的鱼 $t = \frac{m - i}{2}$ 条，答案取 $\max\big(s1[i] + s2[\min(t, cnt2)]\big)$。

关键实现细节

// 按价值降序排序
sort(a+1, a+1+cnt1, greater<int>());
sort(b+1, b+1+cnt2, greater<int>());
// 前缀和
for(int i=1; i<=cnt1; i++) s1[i] = s1[i-1] + a[i];
for(int i=1; i<=cnt2; i++) s2[i] = s2[i-1] + b[i];
// 枚举重量1的数量
for(int i=0; i <= min(cnt1, m); i++) {
    int t = (m - i) / 2;
    ans = max(ans, s1[i] + s2[min(t, cnt2)]);
}

💡 本质是 重量为 1 和 2 的特殊 01 背包，通过贪心排序 + 枚举化为一维扫描。
⚠️ 注意 $t$ 可能超过重 $2$ 鱼的实际数量，要取 $\min$。

三、删数游戏 —— 使剩余数字最大

题目特征

• 给定一个数字字符串 $s$（无前导零），要求删掉 $k$ 个数字，使得剩下的数字组成的 数值最大。
• 剩下长度固定为 $n-k$，目标是 高位尽量大。

贪心策略（相邻比较法）

• 问题等价于：在保留 $n-k$ 位的前提下，让前面的数字尽可能大。
• 每次删除时，从左到右找到第一个满足 $s[i] < s[i+1]$ 的位置，删掉 $s[i]$。
• 如果整个序列非递增（即没有这样的位置），则 删掉最后一个数字。

算法执行过程

while (k--) {
    int flag = 0;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] < s[i+1]) {   // 发现“小-大”，前面的该删
            s.erase(i, 1);
            flag = 1;
            break;
        }
    }
    if (!flag) s.erase(s.size()-1, 1); // 全部非递增，删末尾
}

🧼 易错点：若删完之后结果为空，需输出 "0"；时间复杂度 $O(nk)$，可用单调栈优化到 $O(n)$。

四、字符串升级 —— 有限步数使字典序最大

题目特征

• 给定一个由小写字母组成的字符串 $s$，可以进行 $k$ 次操作。
• 每次操作可以任选一个 不是 'z' 的字符，将它 变为下一个字母（如 'a' → 'b'）。
• 目标是经过恰好 $k$ 次操作（或 $\le k$ 次）后，字符串的 字典序最大。

贪心策略

• 想让字典序最大，必须让 越靠前的字符越大越好。
• 尽量把前面的字符变成 'z'，因为 'z' 是最大字母。
• 对于当前位置 $j$（第一个不是 'z' 的字符），计算它到 'z' 需要的步数 $need = \text{'z'} - s[j]$：
  • 若 $k \ge need$，则把它变成 'z'，$k$ 减去 $need$，继续看下一位。
  • 若 $k < need$，则把当前字符增加 $k$，然后直接结束（因为操作次数用完）。

骨架代码（结合注释还原）

cin >> s >> k;
int n = s.size();
for (int i = 0; i < n && k > 0; i++) {
    if (s[i] == 'z') continue;          // 已是最大，跳过
    int need = 'z' - s[i];              // 升级到 z 还需几步
    if (k >= need) {
        s[i] = 'z';
        k -= need;                      // 消耗步数
    } else {
        s[i] += k;                      // 剩余步数全给它
        k = 0;
    }
}
cout << s << endl;

⚡ 纯贪心，一次遍历，时间复杂度 $O(n)$。

📌 本课小结

记住：贪心的关键是每次做出“当前看起来最优”的选择，并证明这样能得到全局最优。这几种都是非常经典、考试常出的模型，把模板和套路刻进 DNA 里！