贪心：每步都选当前最好¶

什么是贪心？¶

贪心就是走一步看一步，每一步都拿眼前最好的，绝不回头。

排队打水的例子：5 个人接水，耗时分别 3、1、4、2、5 分钟。谁排前面？——耗时短的人排前面。因为他后面所有人都少等一点，总等待时间最小。「每一步都把最短的放前面」这个局部策略，恰好带来全局最优。

贪心的两个关键动作¶

找到「最好」的衡量标准（打水问题：耗时短优先）
按标准排序或逐个挑选（多数情况配合 sort）

警告：贪心不一定对！¶

这是贪心最重要的常识。看一个找硬币的反例：

硬币面额有 1、3、4，凑出 6 元。贪心：先用最大的 4 → 剩 2 → 1+1，共 3 枚。最优：3 + 3，只要 2 枚！

贪心每一步都拿了眼前最大，反而把路堵死了。什么时候能用贪心？当你能说清「眼前这样选，不会坑了后面的选择」——比如打水问题：让耗时短的先走，谁都占不到别人便宜。说不清楚的时候，就老实枚举，或者学第 8 章的动态规划。

CSP 的设计也深谙此道：数据范围小 → 枚举能过；数据范围大 → 背后必有可证明的贪心或 DP。先看范围再定策略。

例题：排队接水¶

题目描述　\(n\) 个人排队接水，第 \(i\) 个人的接水时间为 \(t_i\) 分钟。请安排一个接水顺序，使所有人的等待时间总和最小（每个人要等的就是排在他前面的所有人的接水时间），输出这个最小值。

输入格式　第一行一个整数 \(n\)；第二行 \(n\) 个整数 \(t_i\)。

输出格式　一个整数，最小等待时间总和。

数据范围　\(1 \le n \le 1000\)，\(1 \le t_i \le 10^5\)，总和可能超 int。

样例输入 / 样例输出
5
3 1 4 2 5
20

思路分析　验证一下「短者先行」为什么对：排在第 \(k\) 位的人，前面 \(k-1\) 个人的时间全都要等。所以某人的 \(t\) 每往前挪一位，就有 1 个人少等 \(t\)。把大的 \(t\) 往后放，它造成的等待就影响最少的人——这就是「短者先行」的道理（交换论证）。

算法：升序排序，第 \(i\) 位（从 0 数）的人要等 \(t_0 + t_1 + \cdots + t_{i-1}\)，累加即可。

拿样例验算：排序后 1 2 3 4 5，五个人分别等 \(0, 1, 3, 6, 10\) 分钟，总和 \(20\)。✅ 反过来「长者先行」呢？等 \(0 + 5 + 9 + 12 + 14 = 40\)——整整多一倍。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

long long t[1005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> t[i];
    sort(t, t + n);              // 短者先行

    long long wait = 0;          // 等待总和：1000 × 10^5 级别，必须 long long
    long long prefix = 0;        // 当前人前面所有人的时间之和
    for (int i = 0; i < n; i++) {
        wait += prefix;          // 这个人要等前面所有人
        prefix += t[i];          // 接上他的时间
    }
    cout << wait << endl;
    return 0;
}

口径变体

洛谷完整版 P1223 排队接水的统计口径是「每个人的等待时间含自己的接水时间」且要输出接水顺序。口径以题目描述为准—— 若含本人时间，把 wait += prefix 改成 wait += prefix + t[i] 即可。

贪心题的三道保险

说得出「为什么局部最优不毁全局」（交换论证）
拿反例小数据测一遍（硬币那组 1、3、4 试过没有？）
看清统计口径：是纯等待、还是含服务时间；是总和、还是平均值

动手试一试¶

找硬币反例亲测：写枚举程序求 1、3、4 凑 6 的最少硬币数，验证贪心确实错了
区间调度简化版：读入 \(n\) 个活动的开始/结束时间，输出最多能参加几个不冲突的活动（提示：按结束时间排序，能选就选）
拼木棒：\(n\) 根木棒拼一条最长直线，长度可截断——贪心策略是什么？为什么这里贪心又对了？
思考：排队打水若改成「两人一组抬水」，贪心标准还成立吗？

下一课：有序世界里最锋利的查找——二分查找。