普及二分题https://www.luogu.com.cn/problem/B3629

吃冰棍

题目描述

机器猫喜欢吃冰棍。

买一根冰棍，吃完了会剩一个木棒；每三个木棒可以兑换一个冰棍。兑换出来的冰棍，吃完之后也能剩下一个木棒。

所以，如果机器猫买了 5 根冰棍，他可以吃完之后得到 5 个木棒；拿 3 个木棒兑换 1 根冰棍，余 2 个木棒；吃完兑换来的冰棍之后，手上有 3 个木棒，又能兑换一个冰棍。最后，机器猫实际上吃了 7 个冰棍。

机器猫想要吃到 $n$ 个冰棍，想问最开始至少需要去买多少根冰棍？

输入格式

仅一行，一个正整数，表示 $n$ 。

输出格式

仅一行，一个正整数，表示需要买的冰棍数量。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

数据规模与约定

对于 $100\%$ 的数据， $1\leq n \leq 100000000$ 。

写好check函数就行

cpp
#include <stdio.h>

// check 函数：计算给定初始冰棍数量 x 的情况下，机器猫最终能吃到的冰棍总数
int check(int x) {
    int total = x; // 初始冰棍数量
    int sticks = x; // 初始木棒数量

    while (sticks >= 3) {
        int new_ice_creams = sticks / 3; // 用木棒兑换的冰棍数量
        total += new_ice_creams; // 增加吃到的冰棍总数
        sticks = sticks % 3 + new_ice_creams; // 更新剩余木棒数量
    }

    return total;
}

int main() {
    int n;
    scanf("%d", &n);

    int left = 1, right = n;
    int result = n; // 初始化为 n，因为最多可能需要 n 根冰棍

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid) >= n) {
            result = mid; // 记录当前的 mid 值
            right = mid - 1; // 尝试更小的值
        } else {
            left = mid + 1; // 尝试更大的值
        }
    }

    printf("%d\n", result);

    return 0;
}

目录

吃冰棍