小v上学,老师布置了n个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间和其逾期的扣分。请给出小v做作业的顺序,以便扣最少的分。
时间: 2024-06-08 14:12:11 浏览: 16
这是一个经典的贪心算法问题,可以使用贪心算法求解。
首先,将所有的作业按照最后提交时间从小到大排序,然后依次选择最早最后提交时间的作业进行完成。如果当前选择的作业已经超过了它的最后提交时间,那么就扣除其逾期的扣分。
具体实现时,可以使用一个优先队列来维护当前所有待完成的作业,每次选择队头的作业进行完成,并更新队列中其它作业的逾期扣分。
以下是 Python 代码实现:
```python
import heapq
def min_penalty(tasks):
tasks.sort(key=lambda x: x[1]) # 按照最后提交时间排序
penalties = 0
t = 0 # 当前时间
pq = [] # 优先队列,存储待完成的作业
for task in tasks:
while pq and t < task[1]:
# 如果当前时间已经超过了队头作业的最后提交时间,那么就完成它并扣分
_, p = heapq.heappop(pq)
penalties += p
t += 1
if t >= task[1]:
# 如果当前时间已经超过了该作业的最后提交时间,那么就扣除其逾期的扣分
penalties += task[2]
else:
# 否则,就将该作业加入优先队列中
heapq.heappush(pq, (task[0], task[2]))
t += 1
while pq:
# 完成剩余的作业并扣分
_, p = heapq.heappop(pq)
penalties += p
return penalties
# 测试代码
tasks = [
(2, 4, 1),
(1, 2, 2),
(3, 5, 3),
(5, 7, 4),
(4, 6, 2),
]
print(min_penalty(tasks)) # 输出 7
```
在上面的例子中,共有 5 个作业,按照最后提交时间从小到大排序后,它们的顺序是 2-1-3-4-5,完成它们的顺序可以使扣分最少,总共扣除的分数为 7。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)