B3629 吃冰棍 題解

ShanCreeperPro · 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} 不符合要求，尝试枚举更大数字。