自动搬运

查看原文

来自洛谷，原作者为

	lizhous zxq

搬运于2025-08-24 22:53:09，当前版本为作者最后更新于2023-12-18 20:24:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑枚举公差 $d$，如何求得最少题数 $m$？

贪心的想，我们希望的等差数列是一条直线，而增加的数最少就相当于让直线最低且任意点不低过原序列。扫一遍序列，动态维护当先最少需要增加的数 $f$ 和当前末项大小 $g$，如果下一项 $a_i<g-d$，那么直接把下一项增加 $g-d-a_i$ 即可，否则需要把直线上移 $a_i-(g-d)$。归纳不难得出这样是最优的。

得到结论，令 $f(d)=m$，大胆猜想 $f$ 是单谷函数。

为什么？考虑直线变斜的过程，我们称完全贴合原序列的点为支点，那么不难发现支点是逐渐后移的。又因为斜度的增加，支点前的点贡献一定单调不减，支点后一定单调不增。所以支点前总贡献不降，支点后总共献不增。又因为 $f(d)$ 就是这两个贡献加起来，所以 $f(d)$ 是单谷的。

套上三分即可。

讲得比较抽象。