AcWing 503. Python 二分+差分+标准输入
原题链接
简单
作者:
tangtiexia
,
2024-04-04 18:03:21
,
所有人可见
,
阅读 6
Python代码
import sys
# 标准输入,不用这个,最后2个测试点超时
input = sys.stdin.readline
# 天数、订单数量
n, m = map(int, input().strip().split())
# 下标从0开始,第i天可用于租借的教室数量
day = [0]
day.extend(list(map(int, input().strip().split())))
# 下标从0开始,m份订单, 每行三个正整数,表示[s, t]借d张桌子
orders = [[0, 0, 0]]
orders.extend([list(map(int, input().strip().split())) for _ in range(m)])
def check(mid):
"""
判断是第 mid单让桌子不够了吗
return: boolean
"""
# 差分数组
diff = [0] *(n + 2)
# 第 mid 份订单导致
for i in range(1, mid + 1):
d, s, t = orders[i]
diff[s] += d
diff[t + 1] -= d
# 对差分数组进行合并
for i in range(1, n + 1):
diff[i] += diff[i - 1]
# 判断是否超过可用教室数量
if diff[i] > day[i]:
return False
return True
# 二分,求教室不够用的单子位置
l, r = 0, m
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid # 桌子够用,去单后面
else:
r = mid - 1
# 判断桌子是否够
if r == m:
print(0)
else:
print('-1\n{}'.format(r + 1))