f004 - Error

🔗 前往 ZeroJudge 原題

題目描述

題目要求將輸入的數字 n 分解成若干個固定金額 (1000, 500, 100, 50, 10, 5, 1) 的組合，並以 "金額數量 + 金額數量 + ..." 的格式輸出分解結果。

解題思路

這個問題可以使用貪心演算法解決。從最大的金額開始，盡可能多地使用該金額，然後依次處理較小的金額。程式碼中，a 陣列儲存了所有可能的金額，迴圈遍歷 a 陣列，如果當前金額小於或等於 n，則計算可以使用該金額的次數，並將結果輸出。使用模運算符 % 更新 n 的值，以便處理剩餘金額。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int a[7]={1000,500,100,50,10,5,1};
int main(){
	int n;
	while(cin >> n){
		cout << n << " = ";
		for(int i=0;i<7;++i){
			if(n>=a[i]){
				cout << a[i] << "*" << n/a[i] ; 
				if(n%=a[i])cout << " + ";
			}
		}
		cout << "\n";
	}
}