[AtCoder] [經典競程 90 題] 016 - Minimum Coins(★3)

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_p
題目大意:
有三種幣值的硬幣 $A$, $B$, $C$ ,問要湊出 $N$ 元的話最少要多少硬幣,保證答案使用的總硬幣數不超過 $9999$
因為不超過 $9999$ ,所以直接枚舉 $A$ 用多少跟 $B$ 用多少就自然知道 $C$ 要用多少了。
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	lld n, a, b, c; cin >> n >> a >> b >> c;
	lld ans = n;
	for (lld i = 0; i <= 9999; ++i) {
		for (lld j = 0; j <= 9999; ++j) {
			if (a * i + b * j > n) break;
			lld lef = n - a * i - b * j;
			if (lef % c != 0) continue;
			ans = min(ans, i + j + lef / c);
		}
	}
	cout << ans << '\n';
	return 0;
} 

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology