b911 - 我想跟Kevin借筷子系列4
題目描述
題目要求計算將長度分別為 1 到 n 的 n 支筷子，透過每次選擇一些筷子並同時減少相同長度的方式，將所有筷子砍至長度為 0 所需的最少操作次數。
解題思路
觀察題目可以發現，每次操作的目標是將一些筷子的長度減少相同的數值。最終目標是將所有筷子長度都變為 0。 由於筷子的初始長度為 1 到 n，可以將問題轉化為找到一個最小的 k 值，使得所有數字都能被 k 整除。 實際上，最少操作次數等於 n 的二進位表示中 1 的個數。 例如，n = 2，二進位表示為 10，操作次數為 2。 n = 3，二進位表示為 11，操作次數為 2。 n = 4，二進位表示為 100，操作次數為 1。 n = 5，二進位表示為 101，操作次數為 2。 n = 6，二進位表示為 110，操作次數為 2。 n = 7，二進位表示為 111，操作次數為 3。 n = 8，二進位表示為 1000，操作次數為 1。 因此，最少操作次數等於 log2(n) 的向上取整。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <stdio.h>
#include <math.h>
int main(){
int ans;
while(scanf("%d",&ans)>0)
printf("%d\n",(int)log2(ans)+1);
}