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

好的，我来给您讲一下思路。这是一个经典的贪心算法问题，我们可以按照以下步骤来解决：

1. 构建作业列表，包括作业编号、最后提交时间和逾期扣分。

2. 根据作业的最后提交时间从小到大对作业列表进行排序。

3. 依次完成每个作业，并记录总扣分。

4. 输出作业完成顺序和总扣分。

下面是具体的Python代码实现：

# 构建作业列表
homeworks = []
n = 3
for i in range(n):
    t = int(input("请输入作业 %d 的最后提交时间：" % (i+1)))
    k = int(input("请输入作业 %d 的逾期扣分：" % (i+1)))
    homeworks.append((i+1, t, k))

# 根据最后提交时间从小到大排序
homeworks.sort(key=lambda x: x[1])

# 完成作业并记录总扣分
total_score = 0
order = []
for h in homeworks:
    order.append(h[0])
    if h[1] < len(order):  # 逾期了
        total_score += h[2]

# 输出结果
print("小明完成作业的顺序为：", order)
print("总扣分为：", total_score)

您可以尝试输入样例数据，即最后提交时间为[1, 3, 1]，逾期扣分为[6, 2, 3]，来验证代码的正确性。

相关问题

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

好的，这是一个经典的贪心算法问题。根据题意，我们需要按照最后提交时间从小到大的顺序完成作业，以尽可能避免逾期扣分。代码如下：

def homework(n, t, k):
    """
    :param n: 作业数量
    :param t: 最后提交时间列表
    :param k: 逾期扣分列表
    """
    # 按照最后提交时间从小到大排序
    sorted_homework = sorted(zip(t, k))
    # 已完成作业数量
    finished = 0
    # 总扣分
    total_penalty = 0
    # 遍历每个作业
    for deadline, penalty in sorted_homework:
        if finished < deadline:
            # 在最后提交时间之前完成作业，不扣分
            finished += 1
            total_penalty += penalty
    return total_penalty

# 示例
n = 3
t = [1, 3, 1]
k = [6, 2, 3]
print(homework(n, t, k)) # 输出 5

在这个示例中，最优的做作业顺序是先完成第1个和第3个作业，再完成第2个作业，总共扣分为5分。

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

好的，这个问题也可以使用贪心算法来求解。

我们可以按照最后提交时间从小到大排序，然后依次考虑每个作业是否做或不做。具体的贪心策略是，将所有作业按照最后提交时间从小到大排序，然后依次考虑每个作业，尽可能地在最后提交时间之前完成作业，如果不能在最后提交时间之前完成，则不做此作业。

具体实现如下：

def homework(n, t, k):
    # 将作业按照最后提交时间从小到大排序
    jobs = sorted(zip(t, k))

    # 初始化总扣分和已花时间
    total_penalty = 0
    time = 0

    # 依次考虑每个作业
    for job in jobs:
        # 如果还能在最后提交时间之前完成，则做此作业
        if time + 1 <= job[0]:
            total_penalty += job[1]
            time += 1

    return total_penalty

这个贪心算法的时间复杂度为$O(nlogn)$。