f176 - 湊不到錢大作戰
題目描述
題目要求找出小於等於 k 且最接近 k 的一個數，這個數無法由兩個給定的錢幣面額 m 和 n 湊成。如果所有小於等於 k 的數都可以被 m 和 n 湊成，則輸出 "good"。
解題思路
本題可以使用動態規劃的思想來解決。建立一個布林陣列 a，大小為 k+1，其中 a[i] 表示金額 i 是否可以被 m 和 n 湊成。初始化 a[0] 為 true，表示金額 0 可以被湊成（不使用任何錢幣）。然後，從 0 到 k-n 和 k-m 遍歷，如果 a[i] 為 true，則將 a[i+n] 和 a[i+m] 設為 true，表示金額 i+n 和 i+m 也可以被湊成。最後，從 k 開始倒序遍歷 a 陣列，找到第一個 a[i] 為 false 的索引 i，這個 i 就是答案。如果遍歷完整個陣列都沒有找到 false，則輸出 "good"。
複雜度分析
- 時間複雜度: O(k)
- 空間複雜度: O(k)
程式碼
#include <iostream>
using namespace std;
int n,a[1000005],k,m,t;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> k >> n >> m;
if(n==1||m==1){
cout << "good\n";
}
else{
for(int i=0;i<=k;++i){
a[i]=0;
}
a[0]=1;
int ans=0;
for(int i=0;i<=k-n;++i){
if(a[i])a[i+n]=1;
}
for(int i=0;i<=k-m;++i){
if(a[i])a[i+m]=1;
}
for(int i=k;i>0;--i){
if(a[i]==0){
ans=i;
break;
}
}
if(ans){
cout << ans << "\n";
}
else{
cout << "good\n";
}
}
}
}