对于 \(v_i\)，可以用 \(v_i\times(1+2+\cdots+l)\) 的代价覆盖长为 \(l\) 的连续段，求用 \(n\) 种覆盖 \(L\) 的最小代价。\(1\le n\le 10^5\)，\(1\le L\le 10^9\)。
发现 \(L\le 10^5\) 时很 naive，直接扩展就行。
考虑另外一种 naive 的做法，令 \(dp_i\) 代表覆盖 \(i\) 的最小代价，发现 \(dp_{i+1}\) 一定由 \(dp_i\) 转移得到。设 \(dp_i\) 时长度集合为 \({x_1,x_2,\cdots,x_n}\)，则 \(dp_{i+1}=dp_i+\min_1^n [v_i*(x_i+1)]\)，易证。
发现等同于取前 \(L\) 小，于是考虑这个东西怎么做。
同样很 naive，二分第 \(k\) 小值统计即可。
我们发现 序列合并 是一种非常类似的题，只不过是用堆来拓展。
那么可以二分吗？显然可以。check 时双指针即可。
包括这道题 超级钢琴 也是堆来进行扩展，请自己研究一下二分做法。
标签：二分,10,le,naive,一种,cdots,dp From： https://www.cnblogs.com/BYR-KKK/p/18114497