b150 - NOIP2004 1.津津的储蓄计划

🔗 前往 ZeroJudge 原題

題目描述

題目描述了津津的儲蓄計畫，每月月初收到300元，並根據預算儲蓄，年末媽媽會將儲蓄的錢加上20%還給津津。要求判斷在儲蓄過程中是否會出現資金不足的情況，如果沒有，則計算年末津津擁有的總金額。

解題思路

這題主要使用模擬的方法來解決。我們需要遍歷每個月的預算，模擬津津的儲蓄過程。首先，津津收到300元，然後減去當月的預算。如果餘額小於0，則表示資金不足，輸出當月並結束程式。如果餘額大於等於0，則將餘額的整百部分存入媽媽那裡，並計算剩餘金額。最後，如果沒有出現資金不足的情況，則計算年末媽媽還給津津的錢，並加上津津自己剩下的錢，輸出總金額。

複雜度分析

• 時間複雜度: O(n)，其中 n 是月份數 (12)。程式碼遍歷了12個月的預算。
• 空間複雜度: O(1)。程式碼只使用了固定大小的陣列 m[12] 來儲存預算，空間使用量不隨輸入大小變化。

程式碼

#include <iostream>
using namespace std;
int m[12];
int main(){
	while(cin >> m[0]){
		int ans=0,s=0,c=0;
		for(int i=1;i<12;++i){
			cin >> m[i];
		}
		for(int i=0;i<12;++i){
			ans+=300;
			ans-=m[i];
			if(ans<0){
				cout << -(i+1) << "\n";
				c=1;
				break;
			}
			else{
				s+=ans/100;
				ans%=100;
			}
		}
		if(c==0){
			cout << s*120+ans << "\n";
		}
	}
}