小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。给出示例代码
时间: 2024-02-13 12:01:23 浏览: 8
题目描述比较清晰,可以使用贪心算法来解决。
具体做法是按照最后提交时间从小到大排序,如果最后提交时间相同,则按照逾期扣分从小到大排序。然后依次完成作业,尽量不要让作业逾期。
以下是示例代码实现:
```python
n = int(input())
while n:
# 输入作业信息
t = list(map(int, input().split())) # 最后提交时间
k = list(map(int, input().split())) # 逾期扣分
# 排序
tasks = sorted(zip(t, k))
# 计算总扣分
total = 0
deadline = 0 # 当前最晚提交时间
for task in tasks:
deadline = max(deadline, task[0]) # 更新最晚提交时间
total += task[1] * max(0, deadline - task[0])
print(total)
n = int(input())
```
注意,这里使用了 `zip()` 函数来将最后提交时间和逾期扣分绑定为一个元组,方便排序。同时,计算总扣分时需要注意如果作业没有逾期,则不需要扣分。
相关问题
小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。输入作业数量n、每个作业的最后提交时间t以及逾期扣分k,以输入n=0作为结束,给出python代码
以下是一个使用 Python 实现的代码示例:
```python
while True:
n = int(input("请输入作业数量:"))
if n == 0:
break
t = []
k = []
for i in range(n):
t_i, k_i = map(int, input("请输入第{}个作业的最后提交时间和逾期扣分,以空格分隔:".format(i+1)).split())
t.append(t_i)
k.append(k_i)
# 将所有作业按照最后提交时间从小到大排序,如果最后提交时间相同,则按照逾期扣分从小到大排序
homeworks = [(t[i], k[i]) for i in range(n)]
homeworks = sorted(homeworks, key=lambda x: (x[0], x[1]))
# 按照排好序的顺序一个一个地完成作业
total_score = 0
for i in range(n):
deadline, score = homeworks[i]
if deadline > i + 1: # 如果逾期了
total_score += score
print("小明需要扣除的总分数为:", total_score)
```
这个代码使用了一个无限循环,每次循环中根据输入的作业数量和具体的作业信息计算出小明需要扣除的总分数。当输入作业数量为 0 时,循环结束。
写作业问题 算法小明上学,老师布置了·n·个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间 ti及其逾期的扣分 ki。已知作业 n·=·3,每个作业的最后提交时间 t·=·[1,3,1],作业逾期扣分 k·=·[6,2,
假设小明按照最优策略完成作业,即尽可能地减少扣分,可以使用贪心算法来解决这个问题。具体思路如下:
1. 按照作业的最后提交时间 ti,将作业按照 ti 从小到大排序,作业序列为 [1,3,2]。
2. 遍历作业序列,对于每个作业 i,计算其逾期的时间 di = max(0, ti - i),即最后提交时间减去实际完成时间(如果实际完成时间超过最后提交时间,则 di 为 0)。
3. 计算完成作业 i 所需要的总时间 ti + di,即最后提交时间加上逾期时间,记为 si。
4. 将作业按照完成时间 si 从小到大排序,完成作业的顺序为 [1,3,2]。
5. 计算小明的总扣分 ki_total = sum(ki * max(0, di)),即每个作业的逾期扣分乘上逾期时间的总和。
因此,小明应该按照 [1,3,2] 的顺序完成作业,总扣分为 ki_total = 6 * 0 + 2 * 0 + 4 * 1 = 4 分。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)