贪心算法是通用思想而非C++特性，需用std::sort、priority_queue等手动实现局部最优选择；排序依据决定贪心正确性，如活动选择按结束时间排序后线性扫描，分数背包可贪心而0-1背包不可。
贪心算法不是C++特有，但要用好得懂怎么写
贪心算法本身是思想，不是语言特性。C++里实现它，关键在「每步选当前最优解」的逻辑是否正确落地，而不是调用某个叫 greedy() 的函数——C++标准库没有这个东西。
你真正要做的，是用 std::sort、std::priority_queue 或手动遍历，把「局部最优选择」明确写成循环或条件判断。比如活动选择问题，核心就是按结束时间排序后线性扫描；而背包问题里，分数背包用排序+贪心，0-1背包就不能直接贪心——这点容易误判。
什么时候该用 std::sort 配合贪心
多数经典贪心题（如区间调度、任务安排、硬币找零）都依赖一个排序依据：结束时间、单位价值、截止时间等。排序不是为了好看，而是让后续单次遍历能安全做决策。
- 排序比较函数必须严格弱序，别写
a 当 <code>operator，否则 <code>std::sort行为未定义 - 如果排序键可能重复（比如多个活动结束时间相同），要额外约定：按开始时间升序？还是任意？不明确会导致结果不稳定
- 别在循环里反复排序——O(n²log n) 就不是贪心了，贪心本意是 O(n log n) 预处理 + O(n) 扫描
示例：按结束时间选最多不重叠区间
立即学习“C++免费学习笔记（深入）”；
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
return a[1] < b[1]; // 严格用 <，不是 <=
});
int count = 0, last_end = -1;
for (const auto& inter : intervals) {
if (inter[0] >= last_end) { // 起始 >= 上个结束，可选
++count;
last_end = inter[1];
}
}
为什么 std::priority_queue 常出现在贪心实现里
当「当前最优」不是静态排序能决定的，而是随状态动态变化时，堆比排序更合适。比如合并果子（哈夫曼思想）、最小生成树的Prim算法、会议安排中考虑会议室释放时间。
-
std::priority_queue默认是大根堆，贪心常要小根堆：写成priority_queue<int vector>, greater<int>></int></int> - 别直接往堆里塞原始数据就完事——确认堆顶元素确实代表「当前可选的最优候选」，否则贪心失效
- 堆操作复杂度是 O(log n)，整个流程仍是 O(n log n)，但比先排序再删选更灵活
示例：用最小堆维护可用会议室结束时间
priority_queue<int, vector<int>, greater<int>> rooms; // 小根堆
sort(meetings.begin(), meetings.end());
for (auto& m : meetings) {
if (!rooms.empty() && rooms.top() <= m[0]) {
rooms.pop(); // 释放已结束的会议室
}
rooms.push(m[1]); // 占用到 m[1]
}
贪心失败的典型信号和检查点
代码跑过了样例但交上去WA？不是数据太弱，就是贪心策略本身错了。C++实现再漂亮也救不了错误的数学前提。
- 局部最优不能推出全局最优时，贪心必然失败——比如0-1背包，
value/weight排序后取前k个，反例一抓一大把 - 没验证贪心选择性质（greedy-choice property）和最优子结构（optimal substructure），只是“感觉应该对”，大概率翻车
- 边界没处理：空输入、单元素、全相同值、负数权重……这些地方
std::sort和priority_queue不报错，但逻辑可能崩
真要验证贪心是否适用，手推小规模反例比写测试更快。比如三个活动：[(1,4), (2,3), (3,5)]，按开始时间贪心选第一个，按结束时间贪心选第二个——结果差一个，就知道依据选错了。
