【题目来源】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 木棒。则可得nx⌊x/2⌋即 n⌊3x/2⌋。据此可得x⌈2n/3⌉即 x2n/31等价于x(2n3)/3。【算法代码一】#include iostream using namespace std; int main() { int n; cinn; cout(2*n3)/3endl; return 0; } /* in: 20 out: 14 */【算法代码二】#include bits/stdc.h using namespace std; int main() { int n; cinn; if(n1) cout1endl; if(n2) cout2endl; if(n%30 || n%31) coutn/3*21endl; if(n%32) coutn/3*22endl; } /* in:7 out:5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/144309226https://blog.csdn.net/hnjzsyjyj/article/details/144146636https://blog.csdn.net/yymer214/article/details/143456263https://www.luogu.com.cn/problem/P1304https://www.luogu.com.cn/problem/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 木棒。则可得nx⌊x/2⌋即 n⌊3x/2⌋。据此可得x⌈2n/3⌉即 x2n/31等价于x(2n3)/3。【算法代码一】#include iostream using namespace std; int main() { int n; cinn; cout(2*n3)/3endl; return 0; } /* in: 20 out: 14 */【算法代码二】#include bits/stdc.h using namespace std; int main() { int n; cinn; if(n1) cout1endl; if(n2) cout2endl; if(n%30 || n%31) coutn/3*21endl; if(n%32) coutn/3*22endl; } /* in:7 out:5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/144309226https://blog.csdn.net/hnjzsyjyj/article/details/144146636https://blog.csdn.net/yymer214/article/details/143456263https://www.luogu.com.cn/problem/P1304https://www.luogu.com.cn/problem/B3629
)
