洛谷 B3629：吃冰棍 ← 两种模拟法

【题目来源】
https://www.luogu.com.cn/problem/B3629

【题目描述】
机器猫喜欢吃冰棍。
买一根冰棍，吃完了会剩一个木棒；每三个木棒可以兑换一个冰棍。兑换出来的冰棍，吃完之后也能剩下一个木棒。
所以，如果机器猫买了 5 根冰棍，他可以吃完之后得到 5 个木棒；拿 3 个木棒兑换 1 根冰棍，余 2 个木棒；吃完兑换来的冰棍之后，手上有 3 个木棒，又能兑换一个冰棍。最后，机器猫实际上吃了 7 个冰棍。
机器猫想要吃到 n 个冰棍，想问最开始至少需要去买多少根冰棍？

【输入格式】
仅一行，一个正整数，表示 n。

【输出格式】
仅一行，一个正整数，表示需要买的冰棍数量。

【输入样例1】
7

【输出样例1】
5

【输入样例2】
20

【输出样例2】
14

【数据规模与约定】
对于 100% 的数据，1≤n≤10^8。

【算法分析】
● 本题可以用二分法实现，详见：https://blog.csdn.net/hnjzsyjyj/article/details/144309226
二分法是一种基于‌分治思想‌的高效搜索算法，通过‌两段性划分逐步缩小搜索范围，其核心优势在于将时间复杂度从 O(n) 降至。两段性指区间能被划分为‌两个互补部分‌：一部分满足特定条件，另一部分不满足。二分法的核心在于‌利用两段性快速缩小搜索范围‌，与单调性无必然联系，单调性仅是两段性的特例之一。

● 本题还有相当简单的解法，即通过推导发现规律求解。
设最终吃到的冰棍总数为 n，最初至少购买的冰棍儿数量为 x。
由于每兑换 1 根冰棍儿需消耗 3 木棒，而这根儿兑换而得的冰棍儿的木棒还要留下来，故每兑换一根冰棍儿净消耗 2 木棒。则可得：
n=x+⌊x/2​⌋，即 n=⌊3x/2​⌋。据此，可得x=⌈2n/3​⌉，即 x=2n/3+1，等价于x=(2n+3)/3。

【算法代码一】

#include <iostream> using namespace std; int main() { int n; cin>>n; cout<<(2*n+3)/3<<endl; return 0; } /* in: 20 out: 14 */

【算法代码二】

#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; if(n==1) cout<<1<<endl; if(n==2) cout<<2<<endl; if(n%3==0 || n%3==1) cout<<n/3*2+1<<endl; if(n%3==2) cout<<n/3*2+2<<endl; } /* in:7 out:5 */

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/144309226
https://blog.csdn.net/hnjzsyjyj/article/details/144146636
https://blog.csdn.net/yymer214/article/details/143456263
https://www.luogu.com.cn/problem/P1304
https://www.luogu.com.cn/problem/B3629