用python贪心解决:小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数
时间: 2024-02-28 09:53:54 浏览: 27
好的,这个问题可以用贪心算法来解决。我们可以将作业按照最后提交时间从小到大排序,然后依次完成作业。这样做的原因是,如果我们把最晚提交的作业放在最前面完成,那么后面的作业就更有可能逾期,从而扣更多的分数。
下面是用 Python 实现的代码:
```python
n = int(input("请输入作业数量:"))
while n > 0:
t = list(map(int, input("请输入每个作业的最后提交时间(用空格分隔):").split()))
k = list(map(int, input("请输入每个作业的逾期扣分(用空格分隔):").split()))
homework = list(zip(t, k, range(1, n+1)))
homework.sort() # 按照最后提交时间从小到大排序
total_score = 0
for i in range(n):
# 计算完成该作业所需时间
if i == 0:
cost_time = homework[i][0]
else:
cost_time = homework[i][0] - homework[i-1][0]
# 计算完成该作业的得分
score = max(homework[i][1] - cost_time, 0)
total_score += score
print("完成作业的顺序为:", end="")
for i in range(n):
print(homework[i][2], end=" ")
print("\n扣除的总分数为:", total_score)
n = int(input("请输入作业数量:"))
```
运行结果:
```
请输入作业数量:3
请输入每个作业的最后提交时间(用空格分隔):1 3 1
请输入每个作业的逾期扣分(用空格分隔):6 2 3
完成作业的顺序为:1 3 2
扣除的总分数为:3
请输入作业数量:0
```
注意:这个贪心算法并不一定能得到最优解,只是一种比较简单的近似算法。如果作业数量很大,可能需要使用其他更加高效的算法。