d658 - 11636 - Hello World!

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算，為了印出 N 行 "Hello World!"，最少需要進行多少次複製貼上操作。複製貼上操作每次會將現有的行數翻倍。

解題思路

題目可以轉化為找到最小的 k 值，使得 2^k >= N。 由於每次複製貼上都會將行數翻倍，因此可以使用貪心策略，每次都將行數翻倍，直到達到或超過目標行數。 程式碼中，n 模擬目前的行數，每次迴圈將 n 乘以 2，直到 n 大於或等於目標行數 m。 迴圈次數 i 即為最少複製貼上的次數。

複雜度分析

• 時間複雜度: O(log N)
• 空間複雜度: O(1)

程式碼

#include <iostream>

using namespace std;

int main (){
	
	long long int n=1,m=0,i=0,k=1;
	while(cin >> m){
	if(m>=0){
		while(n<m){
			n*=2;
			i++;
		}
		cout << "Case "<< k << ": " <<i-- << endl;
		k++;
		n=1;m=0;i=0;
	}
	}
}