f044 - 2. 史萊姆生態區 (Slime)

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算最少需要幾天，才能讓史萊姆的數量從 a 增加到至少 b。每天史萊姆的數量會翻倍。

解題思路

這題可以使用二分搜尋法來找到最少的天數。由於史萊姆每天翻倍，我們可以二分搜尋天數的範圍，直到找到史萊姆數量大於等於 b 的最小天數。程式碼中，j 代表史萊姆的數量，從 1 開始，每次翻倍，直到大於等於 b/a + 1。i 記錄了天數。由於題目要求的是 a 變成至少 b，所以需要計算 a * 2^i >= b 的最小 i。

複雜度分析

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

程式碼

#include <stdio.h>
int main(){
int a,b,i=0;
scanf("%d%d",&a,&b);
for(int j=1,br=b/a+1;j!=br;++i)j<<=1;
printf("%d\n", i);
}