题目描述
我也不知道问题出在哪里了
import sys
input=lambda: sys.stdin.readline()
n, m = map(int, input().split())
w = [0] + list(map(int, input().split()))
d, s, t = [0]*(n+1), [0]*(n+1), [0]*(n+1)
for i in range(1, m+1):
d[i], s[i], t[i] = map(int,input().split())
def check(mid):
b = [0]*(n+2)
for i in range(1,mid+1):
b[s[i]] += d[i]
# print(t[i] + 1)
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 = 1
r = m
ans = 0
while l < r:
mid = (l+r)//2
if check(mid):
ans = mid
# print(mid)
l = mid+1
else:
r = mid
if mid==m:
print(0)
else:
print(-1)
print(ans+1)
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla