执行任务赚积分(100)
- 有n个任务需要处理,同一时间只能处理一个任务,处理每个任务所需的时间固定为1;
- 每个任务都有最晚处理时间和积分,在最晚处理时间之前处理完成才可以获取该任务的积分;
- 在有限的时间t内,可以获取的最多积分;
输入描述:
第一行输入n,【1,100】
第二行输入t,表示可用于处理任务的总时间单位,【1,100】
随后的n行,每行两个数值s v,分别表示最晚处理时间和积分;s在【1,100】之间,v在【0,100000】之间;
输出描述:
可获取的最多积分
示例1
输入:
4
3
1 2
1 3
1 4
1 5
输出
5
说明:
所有任务只能在1这个最晚时间处理,取最大积分的任务即可;
示例1
输入:
4
3
1 2
1 3
1 4
3 5
输出:
9
说明:
在1这个时间单位处理积分最多为4的任务;在3这个时间单位处理积分为5的任务,还富余一个时间单位无任务处理;所以最大积分为4+5=9
示例3
输入:
5
2
1 2
1 3
2 5
2 7
4 80
输出:
87
import queue
# 总任务数
n = int(input().strip())
# 可处理任务的总时间单位
t = int(input().strip())
# 存储任务
tasks = []
for i in range(n):
tasks.append(list(map(int, input().strip().split())))
# 任务按照 最晚处理时间 升序排序
tasks = sorted(tasks, key=lambda i: i[0])
print("xxx", tasks)
# 最大积分
max_score = 0
my_queue = queue.PriorityQueue()
time1 = 0
i = 0
while True:
# 任务索引超出
if i >= n:
while my_queue.qsize() > t:
max_score -= my_queue.queue[0]
my_queue.get()
print(max_score)
break
else: # 任务索引内
if time1 < tasks[i][0]:
my_queue.put(tasks[i][1])
time1 += 1
max_score += tasks[i][1]
else:
if my_queue.qsize() > 0:
top = my_queue.queue[0]
if tasks[i][1] > top:
my_queue.get()
my_queue.put(tasks[i][1])
max_score += tasks[i][1] - top
i += 1
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » OD C卷 - 执行任务赚积分
发表评论 取消回复