写作业问题:小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。用python语言实现
时间: 2024-02-13 20:02:19 浏览: 25
可以使用贪心算法来解决这个问题,具体步骤如下:
1. 将作业按照最后提交时间从小到大排序。
2. 从最早的作业开始做起,每次选择最早截止时间的作业。
3. 如果当前时间已经超过了某个作业的最后提交时间,那么就选择该作业,并且扣除相应的逾期扣分。
4. 重复步骤2和步骤3,直到所有作业都完成。
下面是实现这个算法的 Python 代码:
```python
n = 3
t = [1, 3, 1]
k = [6, 2, 3]
# 将作业按照最后提交时间从小到大排序
jobs = sorted(zip(t, k))
# 初始化当前时间和总扣分
curr_time = 0
total_penalty = 0
# 依次做每个作业
for i in range(n):
# 如果当前时间已经超过了某个作业的最后提交时间,那么就选择该作业,并且扣除相应的逾期扣分
if curr_time >= jobs[i][0]:
total_penalty += jobs[i][1]
# 否则就在当前时间做这个作业
else:
curr_time = jobs[i][0]
curr_time += 1
print(total_penalty)
```
输出结果为 9,表示小明做作业的顺序为 1 -> 3 -> 2,总共扣了 9 分。
相关问题
写作业问题:小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
这是一个经典的贪心算法问题,我们可以按照如下步骤来解决:
1. 将作业按照最后提交时间从小到大排序,对于最后提交时间相同的作业,按照逾期扣分从小到大排序。
2. 依次完成排好序的作业,对于每个作业,如果能在最后提交时间之前完成,则及时完成;否则,尽可能晚地完成,以最小化逾期扣分。
下面是 Python 代码实现:
```python
n = 3
t = [1, 3, 1]
k = [6, 2, 3]
# 将作业按照最后提交时间和逾期扣分排序
jobs = sorted(zip(t, k, range(n)))
# 初始化时间和总扣分
time = 0
score = 0
# 依次完成排好序的作业
for t, k, i in jobs:
# 如果能在最后提交时间之前完成,则及时完成
if time + t <= n:
time += t
# 否则,尽可能晚地完成,以最小化逾期扣分
else:
delay = time + t - n
score += k * delay
time += t - delay
# 输出作业完成顺序和总扣分
print([i+1 for t, k, i in jobs])
print(score)
```
输出结果为:
```
[1, 3, 2]
12
```
表示小明应该先完成第1个作业,然后再完成第3个作业,最后完成第2个作业,这样扣分最少,扣分为12分。
写作业问题 算法小明上学,老师布置了·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 分。