AcWing 503. Python版题解(二分+差分)
原题链接
简单
作者:
吕飞雨
,
2024-03-02 00:24:15
,
所有人可见
,
阅读 89
n,m=map(int,input().split())
w=[0]+list(map(int,input().split()))
# dst=[]
d=[0]
s=[0]
t=[0]
for _ in range(m):
dst = list(map(int,input().split()))
d.append(dst[0])
s.append(dst[1])
t.append(dst[2])
def check(mid): # 检查当前订单是否满足要求
b=[0]*(n+m) # 差分数组
for i in range(1,mid+1):
b[s[i]]+=d[i]
b[t[i]+1]-=d[i]
for i in range(1,n+1):
b[i]+=b[i-1]
if b[i]>w[i]:
return False
return True
l,r=0,m
while l<r: # 对订单的数量进行二分,查找有问题的那一个订单
mid=(l+r+1)>>1
if check(mid): # 为真说明这一订单可以满足要求
l=mid # 那么mid前面的订单自然也可以满足要求
else:
r=mid-1
if r == m:
print(0)
else:
print("-1\n{}".format(r+1))