吃冰棍(Eating Popsicles) 题解

思路分析

购买冰棍数越多，最终能吃到的总冰棍数单调不降，满足单调性。在 $[1, n]$ 上二分初始购买数量 $x$，check(x) 直接按题意模拟「每 $3$ 根木棒换 $1$ 根冰棍并新增 $1$ 根木棒」（每次循环木棒数至少减半，$O(\log x)$ 步结束），取满足总数 $\ge n$ 的最小 $x$。总时间复杂度 $O(\log^2 n)$。

参考代码

#include <iostream>
using namespace std;

bool check(long long x, long long n)
{
    long long tot = x, sticks = x;
    while (sticks >= 3)
    {
        long long add = sticks / 3;
        tot += add;
        sticks = (sticks % 3) + add;
        if (tot >= n) return true;
    }
    return tot >= n;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    if (!(cin >> n)) return 0;
    long long l = 1, r = n, ans = n;
    while (l <= r)
    {
        long long mid = (l + r) / 2;
        if (check(mid, n))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}