算法-二分与差分-503.借教室

本文主要是介绍算法-二分与差分-503.借教室，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

思路

1. 代码不超时：限制在10的8次方以内；线段树能处理的数据上限是10^5
2. 二分：具有二段性，第一个订单不满足，后面的订单也不用去考虑
3. 差分（前缀和的逆运算）：题目的要求是将一个区间整体减去一个数，最终去判断是否存在某个数小于零
4. 二分完之后利用差分将前面若干个订单判断一遍，如果前面存在订单小于0，说明不满足
5. AcWing 503. 借教室（寒假每日一题） - AcWing

代码

n, m = map(int, input().split())
r = [0] + list(map(int, input().split()))
d = [0] * (m+5)  
s = [0] * (m+5)  
t = [0] * (m+5)  
b = [] def check(mid):b = [0] * (n+5)  # 将 b 初始化为与 r 相同长度的列表，并全部填充为 0for i in range(1, n+1):b[i] = r[i] - r[i-1]  # 差分数组的初始化for i in range(1, mid+1):  # 处理前 mid 个订单b[s[i]] -= d[i]  # 有订单之后，区间的值要减少 d[i]b[t[i] + 1] += d[i]  # 差分的基本操作for i in range(1, n+1):  # 求差分数组的前缀和，相当于求原数组b[i] += b[i-1]if b[i] < 0:return False  # 说明订单不能满足return Truefor i in range(1, m+1):d[i], s[i], t[i] = map(int, input().split())L, R = 1, m
while L < R:mid = (L + R) >> 1if check(mid)==False:R = midelse:L = mid + 1  
if check(m) :print("0")
else :print("-1")print(R)

这篇关于算法-二分与差分-503.借教室的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---