1715. 桶列表
摘要
Title: 1715. 桶列表
Tag: 差分、扫描线
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1715. 桶列表
-
题意
Farmer John 正在考虑改变他给奶牛分配牛奶桶的方式。
他希望使用尽量少的牛奶桶，请帮助他！
Farmer John 有 N 头奶牛，编号为 1…N。
第 i 头奶牛需要从时刻 si 到时刻 ti 之间挤奶，并且挤奶过程中需要用到 bi 个桶。
多头奶牛可能在同一时刻都在挤奶；每个桶在每个时刻只能供一头奶牛使用。
也就是说，第 i 头奶牛在时刻 si 到时刻 ti 之间挤奶时，如果用到了某个桶，则该桶在这段时间不能被其他奶牛使用。
当然，这个桶在这段时间之外可以被其他奶牛所使用。
为了简化他的工作，FJ 保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的 si 和 ti 各不相同）。
FJ 有一个储藏室，里面有编号为 1、2、3、…… 的桶。
在他的挤奶策略中，当某一头奶牛（比如说，奶牛 i）开始挤奶（在时刻 si），FJ 就跑到储藏室取出编号最小的 bi 个桶分配给第 i 头奶牛用来挤奶。
请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。 -
思路
一看是时刻，就想到用一维扫描线统计最大值即可，三分钟的码量
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25'''
Author: NEFU AB-IN
Date: 2022-02-10 11:44:19
FilePath: \ACM\Acwing\1715.py
LastEditTime: 2022-02-10 11:47:10
'''
a = []
if __name__ == "__main__":
n = int(input())
for i in range(n):
s, t, b = map(int, input().split())
a.append((s, b))
a.append((t, -b))
a.sort()
last, cnt, res = 0, 0, 0
for x, y in a:
cnt += y
last = x
res = max(cnt, res)
print(res)