小明有n个作业需要完成,每个作业需要一天时间完成,每个作业都有一个最后提交时间ti和一个逾期扣分ki。小明需要按照某种顺序完成这些作业,以便扣最少的分数。请设计一个算法,求出小明完成作业的解,然后逐步构建最终的解。
时间: 2024-02-24 07:55:46 浏览: 14
这是一个经典的贪心算法问题,可以采用按最后提交时间排序的贪心策略。
首先,我们将所有作业按照最后提交时间从小到大排序。然后,我们按照排序后的顺序依次完成作业。每次完成作业时,我们计算当前完成作业的扣分,如果当前完成作业已经逾期,则将当前扣分加上逾期扣分;否则,当前扣分不变。最后,将所有扣分加起来即为最终的总扣分。
下面是一个 Python 实现:
```python
from typing import List
def min_penalty(n: int, t: List[int], k: List[int]) -> int:
tasks = sorted(zip(t, k))
penalty = 0
time = 0
for i in range(n):
time += 1
if time > tasks[i][0]:
penalty += tasks[i][1]
return penalty
```
通过多组测试用例可以验证算法的正确性:
```python
assert min_penalty(5, [2, 3, 4, 5, 6], [1, 2, 3, 4, 5]) == 15
assert min_penalty(5, [1, 2, 3, 4, 5], [5, 4, 3, 2, 1]) == 15
assert min_penalty(5, [5, 4, 3, 2, 1], [1, 2, 3, 4, 5]) == 15
assert min_penalty(5, [1, 3, 5, 2, 4], [5, 4, 3, 2, 1]) == 15
assert min_penalty(5, [1, 3, 5, 2, 4], [1, 2, 3, 4, 5]) == 5
```