#10966. The Bucket List 水桶清单
The Bucket List 水桶清单
USACO 2018 December Contest, Bronze
问题 2. 水桶清单
农场主 John 正在考虑改变他为奶牛提供水桶的方式。他认为这种改变最终能够减少水桶的总数,但他不确定到底需要多少个水桶。请帮助他解决这个问题! 农场主 John 有 N 头奶牛(1 ≤ N ≤ 100),编号为 1 到 N。第 i 头奶牛需要在时间 si 到时间 ti 之间进行挤奶,并且需要 bi 个水桶。多个奶牛可能在同一时间段进行挤奶,如果是这样,它们不能共用同一个水桶。也就是说,分配给第 i 头奶牛的水桶,在她的挤奶期间(即从时间 si 到 ti)不能被其他奶牛使用。当然,这个水桶可以在其他时间段用于其他奶牛。为了简化工作,农场主 John 确保在任何给定的时刻,不会有多头奶牛同时开始或结束挤奶(即 si 和 ti 都是不同的)。
农场主 John 的水桶存储室中有按顺序编号的水桶,编号为 1、2、3 等等。在他目前的挤奶策略中,当某头奶牛(例如第 i 头奶牛)开始挤奶(在时间 si),农场主 John 会跑到存储室并取出编号最小的 bi 个水桶来分配给第 i 头奶牛。
请计算农场主 John 为了成功挤奶所有奶牛,至少需要多少个水桶。
输入格式 (文件 blist.in
):
- 第一行输入一个整数 N,表示奶牛的数量。
- 接下来 N 行,每行描述一头奶牛,包含三个整数 si、ti 和 bi,分别表示该奶牛的挤奶开始时间、结束时间和所需的水桶数。si 和 ti 的值都在 1 到 1000 之间,bi 的值在 1 到 10 之间。
输出格式 (文件 blist.out
):
输出一个整数,表示农场主 John 至少需要多少个水桶。
示例输入:
3
4 10 1
8 13 3
2 6 2
示例输出:
4
题目分析:
- 每次奶牛开始挤奶时,需要从存储室中取出一定数量的水桶,如果有多个奶牛在同一时段挤奶,就需要确保水桶不冲突。
- 我们可以按照奶牛的挤奶时间区间进行排序,模拟奶牛的挤奶过程。在每个时刻,检查当前需要的水桶数,并跟踪当前已分配的水桶状态。
- 目标是计算所需的最小水桶数量,保证每个时段内不会出现水桶冲突。