找零钱

经典贪心：用最少的硬币凑出指定金额，每次都先用面值最大且不超过剩余金额的硬币。

比如有 $5$ 元和 $1$ 元，要凑 $8$ 元：先给一张 $5$（剩 $3$），再给三张 $1$，一共 $4$ 枚。凑 $7$ 元则是 $5+1+1=3$ 枚。

int coins[] = {5, 1};   // 从大到小
int need = 8, cnt = 0;
for (int c : coins) {
    cnt += need / c;    // 这种面值能用几枚
    need %= c;          // 剩下多少
}
cout << cnt;            // 最少硬币数

用 need / c 一次算出该面值用几枚，比一枚枚减更快，复杂度只和面值种类有关。

重要提醒：这个贪心不是对所有面值都成立的！ 只有当硬币面值满足特定条件（如我国 $1,2,5,10\dots$ 体系）时，“先拿大的”才一定最优。遇到像 $1,3,4$ 这种面值，贪心就会给出错误答案——这个坑我们后面专门再看。