【題解】Zerojudge c317 - 硬幣問題！前傳

題目連結

題目大意

$T$ 筆詢問，每筆詢問給定兩個硬幣，幣值分別為正整數 $a$ 和 $b$，問有沒有辦法湊出 $x$ 元？

• $1 \leq T \leq 1000$
• $1 \leq b \leq a \leq x \leq 1000$

題解

因為要用最少數量的硬幣，因此幣值較高的硬幣要盡量越多，幣值較小的硬幣盡量越少。從 $\frac{x}{a}$ 開始，如果可以整除則直接輸出，否則就將 $a$ 的個數減少看剩下是否能夠只用 $b$ 湊出來，直到 $a$ 的貨幣數量 $<0$。這時代表不管怎樣用 $a$ 和 $b$ 兩種貨幣都無法湊出 $x$元，因此無解輸出 $-1$。實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int x, a, b;
	cin >> x >> a >> b;
	int cntA = x / a;
	while((x - cntA * a) % b != 0 && cntA >= 0) {
		cntA--;
	}
	if(cntA < 0) {
		cout << "-1\n";
	} else {
		int cntB = (x - cntA * a) / b;
		cout << cntA + cntB << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin >> tt;
	while(tt--) {
		solve();
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge c317 - 硬幣問題！前傳