题目链接
看到严格选 \(k\) 个，不难想到 WQS二分。定义 \(f(x)\) 为分成 \(x\) 段，最多有多少个超过 \(S\) 的。然后你会发现他不是凸的。因为他有很多平段，比如把两个很小的合并不改变答案。
换个方向？ 考虑定义 \(f(x)\) 为有 \(x\) 个超过 \(S\) 的段，最多有多少个段。然后发现这个函数看起来是凸的，你可以先二分有 \(x\) 个超过 \(S\) 的段，然后 WQS 二分求出 \(f(x)\) 的值，复杂度 \(O(nlog^2n)\)。
但是真的要套两层二分吗？考虑把两层二分合起来。我们要求的是最小的 \(x\)，满足 \(f(x)\ge k\)。先二分 \(f(x)\) 的斜率，dp时同时记录下满足段数最多的前提下 最少 有 \(p\) 个超过 \(S\) 的段，然后看一下 \(f(p)\) 的大小和 \(k\) 作比较，就把原来的外层二分去掉了。
要注意的是， \(f(x),f(x+1),f(x+2)\) 可能三点共线，所以 \(p\) 不一定是最前面的大于等于 \(k\) 的地方。最后求答案时要算的是 \(p+\lfloor(f(x)-k)/r\rfloor\),\(r\) 为二分出来的斜率。答案要对 \(k\) 取 min。
凸性的证明？
感性理解的话，每次减少的段一定是越来越大的，所以他是凸的
下面搬运官方题解。
要证明 \(2f(x+1)\ge f(x)+f(x+2)\)
首先可以发现，dp 时选的合法段一定是极短的，也就是无论删除左端点还是右端点，都会使其不合法。
设 \(f(x)\) 选择了 \(a_1\le a_2\cdots\le a_x\)，\(f(x+2)\) 选择了 \(b_1\le b_2\cdots\le b_{x+2}\) 为右端点的极短合法段。设 \(a_0=b_0=0,a_{x+1}=b_{x+3}=n+1\)。一定存在 \(i\) 满足\(a_i\le b_i\le b_{i+1}\le a_{i+1}\),取 \(a_1\cdots a_{i-1},b_{i+1}\cdots b_{p+2}\) 以及 \(b_1\cdots b_i,a_i\cdots a_p\)，这是 \(f(p+1)\) 的两个构造，他们加起来至少是 \(f(x)+f(x+2)\)，得证。