c350 - “綠白黃” 四校聯課

🔗 前往 ZeroJudge 原題

題目描述

題目描述了學長們從三間友校獲得了一些電話，並且可以利用這些電話換取更多電話。每次使用 K 個電話可以換取 W 個電話，且 W < K。目標是計算學長們最終可以獲得的電話總數。

解題思路

這題可以使用貪心策略來解決。一開始學長有 N 個電話，每次使用 K 個電話換 W 個電話，然後將換到的電話加入到可用的電話數量中。這個過程持續進行，直到剩餘的電話數量不足 K 個為止。 程式碼模擬了這個換電話的過程，並計算了總共獲得的電話數量。

複雜度分析

• 時間複雜度: O(N) (最壞情況下，需要迭代 N 次)
• 空間複雜度: O(1) (只使用了常數級別的額外空間)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,b,c;
	while(cin >> a >> b >> c){
		int sum=0;
		sum+=a;
		while(a>=b){
			a-=b;
			sum+=c;
			a+=c;
		}
		cout << sum << "\n";
	}
}