[NFLSPC #6] 等差数列

lizhous · 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) 是单谷的。

套上三分即可。

讲得比较抽象。