CF460C 题解

TernaryTree · 2023-04-17 22:49:00 · 题解

给出一种不需要二分的 \Theta(m\log n) 解法。

将序列看作一个木桶的板子高度。我们想要让这个桶装尽可能多的水，就要把最短的板尽可能变高。这个理论大家想必都从家长或者老师那里多多少少听过

于是我们考虑每次操作找到当前序列最小值中最左边的那个，将其作为一次操作的左端点。若对应的右端点超出范围就让右端点顶齐最右侧。这个可以线段树维护一下。

由于最小值与严格次小值的差大于等于每次操作加上的 1，所以我们感性理解一下这个贪心的正确性：

• 如果我们当前加的区间里没有最小值那么这次操作没有意义。因为最小值是不变的。

• 我们要在最少次操作内消除最小值。

但是到这里还有一个疑问在于如果有多个区间都包含了同样个数的最小值，那么其会不会影响后面的操作的结果。答案是不会。

假设有这样一个数据：

5 2 4
2 1 1 1 114514

观众老爷如果用自己人类的思维想都会觉得先加 [1,4] 是最好的。但是其实加 [2,5] 效果是一样的。为什么呢？

因为最小值每次加一，其它数可以作为陪衬，最终的结果只与最小值有关。这里需要一点感性理解吧！过于严谨的证明这里没有展开其实是我不会。

这样我们使用线段树维护最左的最小值下标就能做到 m\log n 了。

代码在这里：Link。