小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,
时间: 2024-02-24 12:54:08 浏览: 105
好的,我理解了你的问题。你想知道小明完成这些作业的最小扣分是多少。这是一个经典的贪心问题,可以使用贪心算法来解决。
首先,我们需要按照最后提交时间对作业进行排序,以确保我们始终按照最后提交时间的顺序完成作业。然后,我们可以按照以下方式完成作业:
1. 对于每个作业,如果它在最后提交时间之前就完成了,那么我们不会受到任何扣分,直接完成该作业。
2. 如果作业在最后提交时间之后完成,则需要扣除相应的逾期扣分。我们应该尽可能地减少逾期扣分,因此我们应该首先完成逾期扣分最低的作业。
下面是 Python 代码实现:
```
n = int(input())
while n > 0:
t = list(map(int, input().split()))
k = list(map(int, input().split()))
assignments = list(zip(t, k))
assignments.sort()
total_penalty = 0
current_time = 0
for deadline, penalty in assignments:
if current_time <= deadline:
current_time += 1
if current_time > deadline:
total_penalty += penalty
print(total_penalty)
n = int(input())
```
希望这可以回答你的问题!
阅读全文