b911: 我想跟Kevin借筷子系列4

內容

成功許凱皓總是喜新厭舊，日子一天一天過去，他就越想把那些筷子砍掉

他前幾天已經把他的 n 支筷子砍成長度分別為 1、2、3、4 , …. , n

他現在決定把他們砍光，他每一次操作可以從剩下的筷子中挑選一支或者多支，同時砍掉一個相同的長度

例如: 長度分別為 1、2、3 的 3 支筷子，可以把長度為 2 和 3 的筷子同時砍掉 2，得到長度為 1、0、1 的三支筷子

再把長度為 1 的兩支筷子砍掉 1，就把所有筷子砍完了!

成功許凱皓很怕麻煩，他想知道最少要幾次操作才能把所有筷子砍完

輸入

多筆輸入

第一行有一個整數 n (0 <= n <= 10^18)

代表有幾支筷子

3
4

輸出

輸出最少要幾次操作才能把筷子砍完

2
3

解題思路

因為只要長度相同，一次可以砍無限根筷子，而只要砍法正確，大筷子砍完必能將小筷子也砍完，所以再求的其實就是最長筷子最少要砍多少次。

而要求一個筷子最少要砍幾次其實就是不斷的對半砍，砍到剩 1 再砍一次變成 0 就行了。

所以程式目標就是去模擬不斷將筷子對半砍直到砍成 0 的過程，也就是將輸入不斷的除以 2 直到歸 0。

另外上述不斷砍半的過程也可以轉換成數學公式，用公式解

最低次數 = Floor(Log₂n)+1

完整程式碼

連除版

AC (2ms, 104KB)

#include <stdio.h>

int main()
{
    unsigned long long n;
    int count;
    while (scanf(" %llu", &n) == 1)
    {
        count = 0;
        while (n)
        {
            n >>= 1;
            count++;
        }
        printf("%d\n", count);
    }
    return 0;
}

公式解版

AC (2ms, 132KB)

#include <stdio.h>
#include <math.h>

int main()
{
    double n;
    while (scanf(" %lf", &n) == 1)
    {
        printf("%d\n", (int)log2(n) + 1);
    }
    return 0;
}