贪心法：每一步都选最好的，结果可能是最优

贪心法是一种算法策略，它的核心思想是：在每一步决策时，都选择当前看起来最优的选择，并希望通过这样一次次局部最优的选择，最终得到全局最优的结果。就像你每天早上出门前，想带最少的水壶去上学，于是你选容量最大的那个，因为它能装最多水——这就是贪心的想法。

但贪心法不是万能的，它只对满足一定条件的问题有效。下面我们来详细讲解。

一、贪心法的核心思想

贪心法可以总结为两句话：

1. 局部最优选择：每一步只考虑当前情况，做出最有利的决定，不考虑未来。
2. 希望全局最优：认为一系列局部最优的选择会自然导致全局最优。

生活中的例子

例1：找零钱（面额合理时）
你帮妈妈买零食花了8元钱，妈妈给了你一张10元，需要找2元。你钱包里有1元、5角、2角、1角硬币。要凑出2元（20角），你会怎么给？当然是先拿最大的1元（10角），再拿1元（10角）——正好2枚。或者先拿1元，再拿5角、2角、1角、1角、1角？那样太笨了。贪心法就是每次尽量用面额最大的硬币，这样硬币数量最少。因为1元、5角、2角、1角这种面额满足“倍数关系”（每个大面额都是小面额的整数倍），所以贪心能得到最优。

例2：活动选择
周末有多个活动可以参加，每个活动有开始时间和结束时间。你想参加尽可能多的活动，怎么办？聪明的做法是：每次都选结束时间最早的活动，然后跳过与它时间冲突的活动，再继续选剩下的结束时间最早的活动。这样就能参加最多的活动。这也是贪心——每次选结束时间最早的，给自己留下更多时间。

二、什么时候可以用贪心？

贪心法并不是所有问题都能用。它需要问题满足两个性质：

1. 最优子结构

一个问题的最优解包含其子问题的最优解。简单说：如果你能做出当前最优的选择，那么剩下的问题就可以用同样的方法继续求解，最终合并起来就是整体最优。比如找零钱问题中，你选了最大面额后，剩下的金额找零也要用最少的硬币数量，这就是子问题。

2. 贪心选择性质

每一步的贪心选择（即局部最优）能够导致全局最优。有些问题虽然满足最优子结构，但贪心选择不一定正确。比如下面这个反例：

反例：不合理的硬币面额
假设硬币面额是1元、5角、4角、1角，要付8角钱。贪心会先选最大的5角，剩下3角，再选1角、1角、1角，共4枚硬币。但实际上最优解是选两个4角，只要2枚！因为5角不是4角的整数倍，贪心就失败了。所以只有面额满足“贪心选择性质”（比如每个面额都是前一个面额的倍数）时，贪心才有效。

三、CSP-J中常见的贪心题目

在CSP-J竞赛中，贪心常用来解决以下几类问题：

• 活动选择：每次选结束时间最早的活动。
• 区间覆盖：用最少的区间覆盖一条线段，每次选能覆盖当前起点且终点最靠右的区间。
• 部分背包问题：物品可以分割（比如金粉），每次选单位重量价值最高的物品。
• 排队接水问题：让接水时间短的人先接，使总等待时间最短。

四、新手容易犯的错误

1. 盲目使用贪心：拿到问题不验证，直接贪心求解。一定要先判断是否满足贪心选择性质，否则可能得到错误答案。比如上面8角钱的反例。
2. 排序错误：贪心常常需要先排序（比如按结束时间排序、按价值排序），如果排序条件写错，结果就不对。例如活动选择要按结束时间升序，而不是开始时间。
3. 忘记更新状态：比如找零钱时，每次使用硬币后要减去金额，并继续循环，不要忘记更新money变量。
4. 混淆贪心与动态规划：贪心是每一步只做一次选择，而动态规划会考虑所有可能。如果问题不满足贪心性质，可以用动态规划。

五、完整可运行的代码示例

下面是一个活动选择问题的完整代码：假设你有多个活动，每个活动有开始时间和结束时间，求能参加的最多活动数量。贪心策略：按结束时间从小到大排序，然后依次选取不冲突的活动。

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

// 定义活动结构体
struct Activity {
    int start;  // 开始时间
    int end;    // 结束时间
};

// 比较函数：按结束时间升序排序
bool compareByEnd(Activity a, Activity b) {
    return a.end < b.end;
}

int main() {
    // 创建活动列表
    vector<Activity> activities = {
        {1, 4},  // 活动1: 1~4
        {3, 5},  // 活动2: 3~5
        {0, 6},  // 活动3: 0~6
        {5, 7},  // 活动4: 5~7
        {3, 8},  // 活动5: 3~8
        {5, 9},  // 活动6: 5~9
        {6, 10}, // 活动7: 6~10
        {8, 11}, // 活动8: 8~11
        {8, 12}, // 活动9: 8~12
        {2, 13}, // 活动10:2~13
        {12,14}  // 活动11:12~14
    };

    // 按结束时间排序
    sort(activities.begin(), activities.end(), compareByEnd);

    int count = 0;          // 已选活动数量
    int lastEnd = -1;       // 上一个选中活动的结束时间，初始设为-1

    cout << "选中的活动：" << endl;
    for (Activity act : activities) {
        // 如果当前活动的开始时间 >= 上一个活动的结束时间，则不相冲突
        if (act.start >= lastEnd) {
            count++;
            lastEnd = act.end;
            cout << "活动 [" << act.start << "," << act.end << "]" << endl;
        }
    }

    cout << "最多可以参加 " << count << " 个活动" << endl;
    return 0;
}

运行结果：

选中的活动：
活动 [1,4]
活动 [5,7]
活动 [8,11]
活动 [12,14]
最多可以参加 4 个活动

解释：排序后结束时间依次为4,5,6,7,8,9,10,11,12,13,14。从最早结束的开始：选[1,4]；下一个[3,5]开始3<4冲突，跳过；[0,6]开始0<4冲突，跳过；[5,7]开始5>=4，选上，更新结束时间7；以此类推。

六、相关指引

• 贪心法常与排序配合使用，排序是贪心的前置步骤。
• 如果不满足贪心性质，可以尝试动态规划（比如找零钱问题中面额不规律时），或者回溯法（小规模穷举）。
• 在CSP-J中，遇到“选择最多/最少”且“每次选择后剩余部分独立”的问题，优先考虑贪心。

理解贪心法，多练习生活中的决策场景，你就能快速判断一个问题是否可以用贪心解决。记住：贪心不是万能，但用对了就是利器。