简化一下题意,给定 m 个操作,每次给[l,r] 区间减去 h ,问第几次操作会满足当前位置的数 <0
看到这种区间加减的问题,在笔试中,一般可以启发我们用差分解决。
这题可以考虑二分答案后差分,每次二分操作次数 mid,然后进行 mid 操作后,判断当前 a[i] 是否满足条件即可
时间复杂度为 : O(nlogn)
小红有一项特殊技能,可以降低连绵山峰的高度。每次施法,他能够选定一段连续的山峰区域,使得这些山峰的高度均匀降低。现在他想知道,通过有限次施法之后,何时能使得至少有一个山峰的高度降至海平面以下(高度小于等于 0)。已知山峰的数量和施法的次数,请计算出何时可以实现目标。
第一行包含两个正整数 n 和 m,分别表示山峰的数量和施法的次数。
第二行包含 n 个正整数 H1,H2,...,Hn,表示每个山峰的初始高度。
接下来的 m 行,每行包含三个正整数 Li,Ri,hi,表示每次施法作用的山峰区间 [Li,Ri] 和降低的高度 hi。
输出一个整数,表示在第几次施法之后,至少有一个山峰的高度降至海平面以下。
5 4
6 5 3 4 6
1 3 2
4 4 2
3 5 1
1 5 6
3