c079 - 10346 - Peter's Smokes

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Peter 抽菸並將菸蒂收集起來捲新菸的過程。給定初始菸支數 n 和捲新菸所需的菸蒂數 k，要求計算 Peter 總共可以抽多少支菸。

解題思路

這題可以使用貪心策略來解決。Peter 每次都儘可能地將菸蒂捲成新的菸，直到菸蒂數量不足以捲新菸為止。程式碼模擬了這個過程，計算 Peter 總共抽了多少支菸。核心邏輯是每次檢查是否有足夠的菸蒂（大於等於 k），如果有，則捲成新的菸，並更新菸蒂數量和總菸支數。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	int a,b,r;
    while(cin >> a >> b){
    	r+=a;
    	while(a>0){
    		r+=a/b;
    		a=(a%b+a/b);
    		if(a<b){
    			break;
			}
		}
		cout << r << endl;
		r=0;
	}
}