二分 + 差分(或说前缀和其实前綴和更准确一点)
首先二分答案,即取 mid 个人且他们不会冲突
然后O(n) 判断是否冲突
如何判断呢,首先我们发现 一个人的操作相当于是将 一些連续的山削去了一个高度
然后我们可以记录这座山被消了多少高度但这样一次就要 O(N) 总共(n^2)
但是我们发现高度差只有两个地方变了,一个是起始一个是终止
然后这样修改只要改两个地方
话说树状数组 的 区间修改 单点修改也用到了这种思想 区间修改只改两个点
然后就可以O(n) 判断昰否符合条件了
最后输出l+1 如果 l==m 表示 全部都可以选 输出 0
因为每次 差分数组又要重新计算 ,然而其实不用上次算mid 这次算 x
若mid < x 则直接加上这一部分嘚差分
如果不算最后还是要 O(n) 遍历一下看下是否冲突 高度小于 0
这一部分计算其实是均摊 O(n) 的 这样就做到了 O(logn + n)的做法