小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。用python语言贪心算法写出代码
时间: 2024-02-13 14:59:52 浏览: 56
蓝桥杯训练营第一周作业.pdf
好的,根据题目描述,我们可以使用贪心算法来解决该问题。具体而言,我们可以按照最后提交时间从小到大的顺序对作业进行排序,然后依次完成作业。如果当前时间已经超过了某个作业的最后提交时间,那么就必须立即完成该作业,以避免扣分。下面是用 Python 语言实现的代码:
```python
n = int(input()) # 输入作业数量
while n != 0:
# 读入每个作业的最后提交时间和逾期扣分
t = list(map(int, input().split()))
k = list(map(int, input().split()))
# 构造作业列表
jobs = [(t[i], k[i]) for i in range(n)]
# 按照最后提交时间从小到大排序
jobs.sort()
# 初始化当前时间和总扣分
cur_time, total_k = 0, 0
# 依次完成作业
for job in jobs:
# 如果当前时间已经超过了最后提交时间,就必须立即完成该作业
if cur_time > job[0]:
total_k += job[1]
else:
cur_time = job[0]
cur_time += 1
# 输出最小扣分
print(total_k)
# 读入下一个作业数量
n = int(input())
```
可以看到,我们首先通过输入参数 n 来确定需要处理多少组作业数据。然后,在每组作业数据中,我们读入每个作业的最后提交时间和逾期扣分,构造作业列表,并按照最后提交时间从小到大排序。接着,我们依次完成作业,并根据当前时间和最后提交时间以及逾期扣分计算总扣分。最后,输出总扣分即可。
阅读全文