写作业问题：小明上学，老师布置了 n 个作业，每个作业恰好需要一天做完，每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3，每个作业的最后提交时间t = [1,3,1]，作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束，请给出小明做作业的顺序，以便扣最少的分数。

这是一个经典的贪心算法问题，我们可以按照如下步骤来解决：

1. 将作业按照最后提交时间从小到大排序，对于最后提交时间相同的作业，按照逾期扣分从小到大排序。

2. 依次完成排好序的作业，对于每个作业，如果能在最后提交时间之前完成，则及时完成；否则，尽可能晚地完成，以最小化逾期扣分。

下面是 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 分。

小明上学，老师布置了 n 个作业，每个作业恰好需要一天做完，每个作业都有最后提交时间ti及其逾期的扣分ki。输入作业数量n、每个作业的最后提交时间t以及逾期扣分k，以输入n=0作为结束，给出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 时，循环结束。