贪心CSP-J

💡 核心思想

贪心算法在每一步选择中都做出当前看起来最优的选择，期望局部最优能导致全局最优。贪心不是对所有问题都有效，但一旦可以贪心，代码通常非常简洁。关键是要能证明"局部最优 → 全局最优"。

🎯 直觉理解

想象你是收银员，要给顾客找零，用最少的硬币。贪心策略是"每次给最大面额的硬币"。对于人民币面额（1,5,10,50,100）这个贪心是对的。但如果面额是 {1,3,4}，要找6块——贪心会 4+1+1=3枚，但最优是 3+3=2枚。所以贪心不一定对，需要验证。

📝 算法流程

1. 确定贪心策略：每步选择什么？
2. 证明正确性：交换论证/归纳/反证
3. 实现：通常涉及排序+逐个处理

$$\text{贪心正确性需要证明：局部最优选择不会影响全局最优解的存在}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// 经典贪心：区间调度（最多选多少不重叠区间）
int main() {
    int n; cin >> n;
    vector<pair<int,int>> seg(n);
    for (auto& [l, r] : seg) cin >> l >> r;
    // 按右端点排序，每次选结束最早的
    sort(seg.begin(), seg.end(), [](auto& a, auto& b) { return a.second < b.second; });
    int cnt = 0, end = INT_MIN;
    for (auto& [l, r] : seg) {
        if (l >= end) { cnt++; end = r; }
    }
    cout << cnt << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目