小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。请用python贪心算法解决以上问题
时间: 2024-02-19 21:57:19 浏览: 27
可以采用贪心算法中的“最小化最大值”策略来解决这个问题。具体来说,我们将所有的作业按照最后提交时间从小到大排序,然后依次选择每个作业,并且尽可能地在其最后提交时间之前完成,以最小化其逾期扣分。
以下是Python代码实现:
```python
n = int(input("请输入作业数量:"))
if n == 0:
exit()
# 输入每个作业的最后提交时间和逾期扣分
t = []
k = []
for i in range(n):
t_i, k_i = map(int, input(f"请输入第{i+1}个作业的最后提交时间和逾期扣分:").split())
t.append(t_i)
k.append(k_i)
# 按照最后提交时间从小到大排序
homeworks = sorted(zip(t, k))
# 依次选择每个作业,并且尽可能地在其最后提交时间之前完成
time = 0
total_score = 0
for t_i, k_i in homeworks:
time += 1
if time <= t_i:
total_score += k_i
print(f"小明做作业的顺序为:{homeworks}")
print(f"扣分最少为:{total_score}")
```
输入样例:
```
请输入作业数量:3
请输入第1个作业的最后提交时间和逾期扣分:1 6
请输入第2个作业的最后提交时间和逾期扣分:3 2
请输入第3个作业的最后提交时间和逾期扣分:1 3
```
输出结果:
```
小明做作业的顺序为:[(1, 6), (1, 3), (3, 2)]
扣分最少为:5
```