自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:02，当前版本为作者最后更新于2022-05-15 19:44:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3629 吃冰棍 題解

管理员注：

阅读本文章前，请先阅读$\ \texttt{ShanCreeper}$ B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

点赞上文章即代表您已阅读并熟知其内容。

首先我们来讲一个东西：函数单调性。

有一种函数，满足 $x$ 越大 $f(x)$ 越大。

我们称这样的函数时单调递增的。

在数学中，我们都知道 $f(x)=x^2$ 这个函数在 $x>0$ 的部分时 $f(x)$ 随着 $x$ 的增大而增大，即在 $x>0$ 的范围内单调递增。

形象化的讲：对于任意 $a>b$，有 $f(a) \ge f(b)$。

有一个常用结论：

• 单调递增的函数，可以通过二分法找到最大的 $f(x) \leq n$ 的 $x$。

方法：

• 去 $\texttt{mid}$，如果 $f(\texttt{mid})$ 比 $n$ 小，就找右区间，否则找左区间。

形象化的讲：如果一个问题的收益函数是单调的，那这道题可能能用二分找到满足要求的最小代价。

回到这道题：

• 设这道题要买冰棍数量为 $\texttt{cost}$，不难发现，受益函数 $f(\texttt{cost})$，即买的冰棍越多，吃到的冰棍也就越多。

• 即，寻找最小的 $\texttt{cost}$，使 $f(\texttt{cost}) \ge n$。

我们可以定义函数 calc 循环模拟，把棒子换冰棍，继续吃。

然后在主函数开始二分：

• 如果 $\texttt{mid}$ 符合要求，记录答案，然后枚举更小数字；
• 如果 $\texttt{mid}$ 不符合要求，尝试枚举更大数字。