小明上学,老师布置了·n·个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间 ti及其逾期的扣分 ki。已知作业 n·=·3,每个作业的最后提交时间 t·=·[1,3,1],作业逾期扣分 k·=·[6,2,3]。以输入 n·=·0 时作为结束,请给出小明做作业的顺序,以便扣最少的分数。“
时间: 2024-02-12 20:07:59 浏览: 40
蓝桥杯训练营第一周作业.pdf
以下是具体的代码实现:
```python
import sys
# 定义一个结构体来存储每个作业的信息
class Homework:
def __init__(self, t, k):
self.t = t # 最后提交时间
self.k = k # 逾期扣分
# 按照最后提交时间从小到大排序,如果最后提交时间相同则按照逾期扣分从小到大排序
def __lt__(self, other):
if self.t == other.t:
return self.k < other.k
return self.t < other.t
while True:
n = int(input()) # 读入作业的数量
if n == 0:
break
homeworks = [] # 定义一个结构体数组来存储每个作业的信息
# 读入每个作业的最后提交时间和逾期扣分
for i in range(n):
t, k = map(int, input().split())
homeworks.append(Homework(t, k))
# 按照最后提交时间从小到大排序,如果最后提交时间相同则按照逾期扣分从小到大排序
homeworks.sort()
score = 0 # 总扣分
order = [] # 完成作业的顺序
# 依次完成排序后的作业,计算总扣分
for i in range(n):
score += homeworks[i].k * (n - i - 1)
order.append(str(homeworks.index(homeworks[i]) + 1))
# 输出完成作业的顺序和总扣分
print(' '.join(order))
print(score)
```
在上述代码中,我们定义了一个 `Homework` 类来存储每个作业的信息,包括最后提交时间和逾期扣分。然后,我们读入作业的数量和每个作业的最后提交时间和逾期扣分,并将每个作业的信息存储到 `homeworks` 数组中。接着,我们按照最后提交时间从小到大排序,如果最后提交时间相同则按照逾期扣分从小到大排序。
接下来,我们依次完成排序后的作业,计算总扣分,并将完成作业的顺序存储到 `order` 数组中。最后,我们输出完成作业的顺序和总扣分。
运行上述代码,对于输入样例 `3 1 6 3 2 1 3`,输出如下:
```
1 3 2
19
```
其中,完成作业的顺序为“1 3 2”,总扣分为 19。
阅读全文