解题思路

“一尺之棰，日取其半，万世不竭。”意思是：一根木棍，每天锯掉一半，永远也锯不完。

题目问的是：第几天的时候，木棍长度会变成 1？

先来看样例，木棍长度 n = 100：

所以答案是第 7 天。

做法很简单：

1. 用一个变量 day 记录天数，一开始是第 1 天（因为第 1 天长度还是 n，不用锯）；
2. 只要长度还大于 1，就把长度除以 2（向下取整），同时 day 加 1；
3. 长度变成 1 的时候，循环结束，输出 day。

参考代码

// P4430 一尺之棰：木棍每天锯掉一半（向下取整），求第几天长度变为1
#include <iostream>
using namespace std;

int main() {
    int n; // 木棍初始长度
    cin >> n;

    int day = 1;      // 第一天长度就是 n，所以从第 1 天开始数
    while (n > 1) {   // 只要长度还没到 1，就继续锯
        n = n / 2;    // 每天锯掉一半，向下取整
        day++;        // 天数加一
    }

    cout << day << endl; // 输出变成长度 1 时的天数
    return 0;
}

复杂度分析

• 木棍长度每次除以 2，大约循环 log2(n) 次，n 最大是 10000，所以非常快。时间复杂度是 O(log n)。
• 只用了几个变量，空间复杂度是 O(1)。