阅读量:0
1.题目描述
机器猫喜欢吃冰棍。
买一根冰棍，吃完了会剩一个木棒;每三个木棒可以兑换一个冰棍。兑换出来的冰棍，吃完之后也能剩下一个木棒。
所以，如果机器猫买了5根冰棍，他可以吃完之后得到5个木棒;拿3个木棒兑换1根冰棍，余2个木棒;吃完兑换来的冰棍之后，手上有3个木棒，又能兑换一个冰棍。最后，机器猫实际上吃了7个冰棍。
机器猫想要吃到 几 个冰棍，想问最开始至少需要去买多少根冰棍?
2.输入格式
仅一行，一个正整数，表示 n。
3.输出格式
仅一行，一个正整数，表示需要买的冰棍数量。
4.输入输出样例
输入1：
7输出1：
5输入2：
20输出2：
145.说明/提示
数据规模与约定
对于 100% 的数据，1 <n< 100000000.
代码：
#include <stdio.h> int main() { long long n; scanf("%lld", &n); long long left = 0, right = n; // 最少0根，最多n根 long long result = n; while (left <= right) { long long mid = left + (right - left) / 2; long long totalIceCreams = mid; // 起始购买的冰棍数量 long long sticks = mid; // 吃完后剩下的木棒 // 计算可以吃到多少冰棍 while (sticks >= 3) { long long newIceCreams = sticks / 3; totalIceCreams += newIceCreams; sticks = sticks % 3 + newIceCreams; // 剩下的木棒加上新的木棒 } if (totalIceCreams >= n) { result = mid; // 可以满足条件，记录结果 right = mid - 1; // 尝试更少的冰棍 } else { left = mid + 1; // 需要更多的冰棍 } } printf("%lld\n", result); return 0; } 