a536 - 11689 - Soda Surpler

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Tim 透過回收空汽水瓶換取汽水的情況。給定 Tim 初始擁有的空瓶數 e、當天收集到的空瓶數 f，以及 c 個空瓶可以換一瓶汽水的條件，計算 Tim 最多可以喝到多少瓶汽水。

解題思路

這個問題可以使用貪心策略解決。Tim 應該盡可能地用空瓶換取汽水，直到無法再換為止。程式碼模擬了這個過程：首先計算 Tim 初始擁有的空瓶加上當天收集到的空瓶總數。然後，在空瓶總數大於等於 c 的情況下，不斷地用空瓶換取汽水，並將換到的汽水（即空瓶）加入到空瓶總數中。這個過程重複進行，直到空瓶總數不足以換取一瓶汽水為止。

複雜度分析

• 時間複雜度: O(t * n)，其中 t 是測試案例的數量，n 是每次迭代的次數，在最壞情況下，n 取決於初始空瓶數和收集到的空瓶數，但由於輸入限制，n 的最大值相對較小，可以視為常數。
• 空間複雜度: O(1)，程式碼只使用了幾個整數變數，空間複雜度是常數級別。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
    int t,e,f,c,sum;
    while(cin>>t){
        for(int i=0;i<t;i++){
            cin>>e>>f>>c;
            sum=0;
            e += f;
            while(e/c){
                sum += e/c;
                e =e/c+e%c;
            }
            cout<<sum<<'\n';
        }
    }
}