中 · 贪心

最少硬币数

收银员不做规划：拿起装得下的最大硬币，一次又一次。这个策略 —— 每步都拿当前最优 —— 就是贪心，而且在这套硬币系统里，它可以被证明是最优的。

一句话答案先看 25 能装几个，再 10、再 5、最后 1：<code>amount / 25</code> 枚 25，金额换成 <code>amount % 25</code>，依此类推。四行，不用搜索。

题目

输入: 一个整数 amount（1 ≤ amount ≤ 100000），要支付的分数。

输出: 凑出这个金额所需的最少硬币数（面值 25、10、5、1）。

样例:

输入输出
302
999
11

贪心不是自然法则 —— 它是这套面值的性质。题解之后你会遇到一套让同一策略翻车的硬币，这正是这道题背后藏着的面试题。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 除法就是批量操作

amount / 25 就是一次能装下多少枚 25 —— 根本不需要对硬币写循环。拿完之后，剩下要付的是 amount % 25。对 10、对 5 重复；最后剩下多少，就得用多少枚 1。

提示 2 — 为什么「先拿最大的」在这里是最优的

最优解里，1 至多 4 枚（5 枚就换成 5），5 至多 1 枚（2 枚就换成 10），而 25 装得下时，10+10+5 的组合不比一枚 25 省（10+10+5 = 25）。按面值数到这些上限为止，剩下的全部换成 25 —— 这正是贪心的选择。证明就是这笔计数；贪心四行就把它算出来了。

提示 3 — 知道贪心什么时候会翻车

把同一策略用到面值 {4, 3, 1}、金额 6 上：贪心拿 4+1+1 = 3 枚，而 3+3 只要 2 枚。贪心只在 25/10/5/1 这类规范系统里保证最优。面试官问「这永远对吗？」，这个例子就是答案。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int coins = 0;

    coins += amount / 25; amount %= 25;
    coins += amount / 10; amount %= 10;
    coins += amount / 5;  amount %= 5;
    coins += amount;      // the rest is paid in 1s

    cout << coins << endl;
    return 0;
}

贪心在这里成立，是因为这套面值允许它。当它不成立时 —— 上面的 {4, 3, 1}，或者真实货币的各种怪癖 —— 你就得搜索，标准升级路线是动态规划。在那之前，先见另一个「用结构换搜索」的想法：区间求和 花 O(n) 做一次准备，之后每个问题 O(1) 回答，和贪心做的是同一笔交易。

深度解析

为什么这样做对

拿起装得下的最大硬币，重复。对 25/10/5/1 这可以证明是最优的：最优解里 1 不超过 4 枚、5 不超过 1 枚、（在 25 装得下时）「两个 10 加一个 5」不优于一枚 25 —— 超过这些上限的面额必须是 25，这正是贪心先拿的东西。

代价

四次除法四次取余：时间和空间都是 O(1)，与金额无关。一般版本（任意面值、问金额 X 能否支付）需要动态规划，O(amount × 硬币数)。

常见错法

  • 以为贪心永远最优。面值 {4, 3, 1}、金额 6 时它付 4+1+1（三枚），而 3+3 只要两枚 —— 贪心只在规范系统里安全。
  • 一枚一枚循环（while (amount >= 25) { coins++; amount -= 25; }）而不用除法。答案一样，但 / 和 % 本来就是这个循环的一步到位版。

下一步

「付一次、答多次」的交易在 区间求和 里继续 —— 准备一次，之后每个查询 O(1)。

记住这两句

  • 贪心 = 每步拿当前最优；按面值系统证明，别假设。
  • 面值 c 一次能装 amount / c 枚；剩下的是 amount % c。
🐞 这段是错的 —— 点开,亲手让它挂一次

把剩下的零头丢了 —— 1 分硬币从来没被数进去

#include <iostream>
using namespace std;

int main() {
    int amount;
    cin >> amount;
    int coins = 0;
    coins += amount / 25; amount %= 25;
    coins += amount / 10; amount %= 10;
    coins += amount / 5;
    cout << coins << endl;
    return 0;
}