最少硬币数
有任意多枚 500 韩元、100 韩元、50 韩元、10 韩元的硬币。
输出凑出恰好 n 韩元所需硬币数的最小值。
- 输入
- 10 ≤ n ≤ 1,000,000,000，且 n 是 10 的倍数。
- 输出
- 硬币数的最小值
1880
10
40
4
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
贪心：从最大的硬币开始用商那么多枚，再处理余数。
这里每种硬币都是下一种较小硬币的倍数（500 = 5×100，100 = 2×50，50 = 5×10），所以贪心一定最优；若硬币是 10、40、50，凑 80 时 40+40（2 枚）比 50+10+10+10（4 枚）少，贪心就不行。
语言差别在除法：C、C++、Java、C# 的 int / int 和 Python 的 // 得到商，而 JavaScript、TypeScript 的 / 会除出小数（1880 / 500 = 3.76），需要 Math.floor。
Craykon 的 / 也会除出小数，所以用 数学.商(n, coin)；余数在各语言里都是 %。
顺序也重要：从小硬币开始就全变成 10 韩元了。
n = int(input())count = 0for coin in [500, 100, 50, 10]: count += n // coin n %= coinprint(count)let n = Number(require("fs").readFileSync(0, "utf8").trim());let count = 0;for (const coin of [500, 100, 50, 10]) { count += Math.floor(n / coin); n %= coin;}console.log(count);import { readFileSync } from "node:fs";let n: number = Number(readFileSync(0, "utf8").trim());let count = 0;for (const coin of [500, 100, 50, 10]) { count += Math.floor(n / coin); n %= coin;}console.log(count);import java.util.Scanner; public class Main { public static void main(String[] args) { int n = new Scanner(System.in).nextInt(); int count = 0; for (int coin : new int[] {500, 100, 50, 10}) { count += n / coin; n %= coin; } System.out.println(count); }}using System; class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); int count = 0; foreach (int coin in new[] { 500, 100, 50, 10 }) { count += n / coin; n %= coin; } Console.WriteLine(count); }}#include <iostream> int main() { int n, count = 0; std::cin >> n; for (int coin : {500, 100, 50, 10}) { count += n / coin; n %= coin; } std::cout << count << '\n';}#include <stdio.h> int main(void) { int n, count = 0; const int coins[] = {500, 100, 50, 10}; scanf("%d", &n); for (int i = 0; i < 4; i++) { count += n / coins[i]; n %= coins[i]; } printf("%d\n", count); return 0;}n = 控制台.读行().转数字();count = 0;遍历 (coin 在 [500, 100, 50, 10]){ count += 数学.商(n, coin); n = n % coin;}控制台.输出(count);