贪心是什么

贪心（Greedy）是一种解题策略：每一步都选“当前看起来最好”的那个选择，寄望这些局部最优累积起来，正好得到全局最优。它像走一步看一步、只顾眼前、绝不回头。

比如要凑最少硬币，每次都先拿面值最大的；要参加最多活动，每次都选结束最早的。做法通常是先按某个标准排序，再从头扫一遍依次做决定。

sort(a, a + n, cmp);   // 先按贪心标准排序
for (int i = 0; i < n; i++) {
    if (can_take(a[i])) take(a[i]);   // 每步取当前最优
}

贪心的优点是简单、快，一般只要 $O(n\log n)$（排序主导）。

但它有个大前提：局部最优必须能推出全局最优，这并不总成立。有的问题贪心恰好正确（如活动选择），有的会翻车（如某些硬币面值）。所以用贪心前，最好能想清楚、甚至证明它为什么对，不能想当然。