问题描述

小红有一项特殊技能，可以降低连绵山峰的高度。每次施法，他能够选定一段连续的山峰区域，使得这些山峰的高度均匀降低。现在他想知道，通过有限次施法之后，何时能使得至少有一个山峰的高度降至海平面以下（高度小于等于 0）。已知山峰的数量和施法的次数，请计算出何时可以实现目标。

题解

简化一下题意，给定 $m$ 个操作，每次给$[l, r]$ 区间减去 $h$ ，问第几次操作会满足当前位置的数 $< 0$

看到这种区间加减的问题，在笔试中，一般可以启发我们用差分解决。

这题可以考虑二分答案后差分，每次二分操作次数 $mid$，然后进行 $mid$ 操作后，判断当前 $a[i]$ 是否满足条件即可

时间复杂度为 : $O(n \log n)$