小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
时间: 2024-02-15 07:04:35 浏览: 104
好的,根据题目描述,这是一道贪心算法的题目。我们可以按照以下步骤来解决问题:
1. 将作业按照最后提交时间从小到大排序。
2. 从头开始遍历作业,对于每个作业,计算其逾期后每天的扣分,将其按照扣分从小到大排序。
3. 选择扣分最少的作业完成,并更新当前时间。
4. 重复步骤3,直到所有作业都完成。
根据上述步骤,可以得到以下代码实现:
```python
n = 3
t = [1, 3, 1]
k = [6, 2, 3]
# 将作业按照最后提交时间从小到大排序
jobs = sorted(zip(t, k))
# 记录当前时间和总扣分
time = 0
total_penalty = 0
# 遍历每个作业
for deadline, penalty in jobs:
# 计算逾期后每天的扣分
penalty_per_day = penalty // deadline if deadline != 0 else penalty
# 计算完成该作业的最晚时间
end_time = min(deadline, n - time)
# 选择扣分最少的作业完成
job_penalty = min(penalty_per_day * i for i in range(end_time + 1))
total_penalty += job_penalty
# 更新当前时间
time += 1
print(total_penalty)
```
输出结果为5,表示小明完成作业的最小扣分为5。完成顺序为第1个作业、第3个作业、第2个作业。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)