b860 - 獨角蟲進化計算器

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在給定的糖果數量和獨角蟲數量下，最多可以進化多少隻獨角蟲。進化一隻獨角蟲需要 12 顆糖果，進化後會獲得 1 顆糖果。可以透過補獲獨角蟲 (每隻 3 顆糖果) 或傳送獨角蟲/鐵殼蛹 (每隻 1 顆糖果) 來獲取糖果。

解題思路

這個問題可以使用貪心策略來解決。優先使用糖果進化獨角蟲，直到糖果不足為止。然後，利用剩餘的獨角蟲和已經進化成的鐵殼蛹來獲取更多的糖果，再次嘗試進化。這個過程重複進行，直到無法再進化任何獨角蟲。

程式碼模擬了這個過程。a 代表目前的糖果數量，b 代表目前的獨角蟲數量，c 代表已進化的獨角蟲數量。迴圈持續進行，直到糖果或獨角蟲數量為 0。如果糖果數量大於等於 12，則進化一隻獨角蟲，糖果數量減 11 (用掉 12 顆，得到 1 顆)，已進化數量加 1。否則，使用一隻獨角蟲換取糖果，糖果數量加 1，獨角蟲數量減 1。

複雜度分析

• 時間複雜度: O(n)，其中 n 是糖果和獨角蟲的總數。最壞情況下，迴圈會執行 n 次。
• 空間複雜度: O(1)，程式碼只使用了幾個整數變數，空間使用是常數級別。

程式碼

#include <iostream>
using namespace std;
int main(int argc, char** argv){
	int a,b,c=0;
	cin>>a>>b;
	while(b&&a){
		if(a>=12){
			a-=11;
			c++;
		}
		else{
			a++;
			b--;
		}
	}
	cout<<c<<endl;
}