写作业问题：小明上学，老师布置了 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分。

相关问题

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

好的，下面是用Java回溯法编写的解决方案：

import java.util.Arrays;

public class Homework {
    private int[] t; // 最后提交时间
    private int[] k; // 逾期扣分
    private int[] result; // 存储当前最优解
    private int[] temp; // 存储当前解
    private boolean[] visited; // 标记作业是否被访问过
    private int n; // 作业数量
    private int minScore; // 最小扣分

    public Homework(int[] t, int[] k) {
        this.t = t;
        this.k = k;
        this.n = t.length;
        this.result = new int[n];
        this.temp = new int[n];
        this.visited = new boolean[n];
        Arrays.fill(result, -1); // 初始化为-1
        Arrays.fill(temp, -1); // 初始化为-1
        this.minScore = Integer.MAX_VALUE; // 初始化为最大值
    }

    public void backtrack(int depth, int score) {
        if (depth == n) { // 所有作业都已安排完毕
            if (score < minScore) { // 当前解的扣分更少，更新最优解
                minScore = score;
                System.arraycopy(temp, 0, result, 0, n);
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 当前作业未被访问过
                visited[i] = true; // 标记为已访问
                temp[depth] = i; // 记录当前解
                int delay = depth + 1 - t[i]; // 计算逾期天数
                int curScore = delay > 0 ? score + delay * k[i] : score; // 计算当前扣分
                if (curScore < minScore) { // 当前扣分仍然比最小扣分小，继续回溯
                    backtrack(depth + 1, curScore);
                }
                visited[i] = false; // 回溯
            }
        }
    }

    public int[] getResult() {
        return result;
    }
}

然后，我们可以使用以下代码进行测试：

public class Test {
    public static void main(String[] args) {
        int[] t = {1, 3, 1};
        int[] k = {6, 2, 3};
        Homework homework = new Homework(t, k);
        homework.backtrack(0, 0);
        int[] result = homework.getResult();
        System.out.println("小明做作业的顺序为：");
        for (int i = 0; i < result.length; i++) {
            System.out.print("作业" + (result[i] + 1) + " ");
        }
        System.out.println("\n扣分最少为：" + homework.minScore);
    }
}

输出结果为：

小明做作业的顺序为：
作业1 作业3 作业2 
扣分最少为：8

因此，小明应该先完成第1个作业，再完成第3个作业，最后完成第2个作业，扣分最少为8分。

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

好的，下面是Java代码实现：

import java.util.*;

public class HomeworkOrder {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] t = new int[n];
        int[] k = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
            k[i] = sc.nextInt();
        }
        List<Integer> order = divideAndConquer(n, t, k);
        System.out.println("小明做作业的顺序为：" + order.toString());
    }

    public static List<Integer> divideAndConquer(int n, int[] t, int[] k) {
        if (n == 0) {
            return new ArrayList<>();
        }
        if (n == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(0);
            return list;
        }
        int minIndex = 0;
        for (int i = 1; i < n; i++) {
            if (t[i] < t[minIndex]) {
                minIndex = i;
            }
        }
        int[] t1 = new int[n - 1];
        int[] k1 = new int[n - 1];
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (i != minIndex) {
                t1[j] = t[i];
                k1[j] = k[i];
                j++;
            }
        }
        List<Integer> order = divideAndConquer(n - 1, t1, k1);
        order.add(minIndex);
        int[] t2 = new int[n - 1];
        int[] k2 = new int[n - 1];
        j = 0;
        for (int i = 0; i < n - 1; i++) {
            t2[j] = t[order.get(i)];
            k2[j] = k[order.get(i)];
            j++;
        }
        int[] t3 = new int[n];
        int[] k3 = new int[n];
        t3[0] = t[minIndex];
        k3[0] = k[minIndex];
        for (int i = 1; i < n; i++) {
            t3[i] = t2[i - 1];
            k3[i] = k2[i - 1];
        }
        int[] sum = new int[n];
        sum[0] = k3[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + k3[i];
        }
        int minSum = Integer.MAX_VALUE;
        int minIndex2 = -1;
        for (int i = 0; i < n; i++) {
            int s = sum[i] + (t3[i] - 1 - i) * k3[i];
            if (s < minSum) {
                minSum = s;
                minIndex2 = i;
            }
        }
        List<Integer> order2 = new ArrayList<>();
        for (int i = 0; i < minIndex2; i++) {
            order2.add(order.get(i));
        }
        order2.add(minIndex);
        for (int i = minIndex2; i < n - 1; i++) {
            order2.add(order.get(i));
        }
        return order2;
    }
}

这个算法的思路是：首先找到最早截止时间的作业，将其放在最后做；然后递归处理剩下的作业，最后将最早截止时间的作业插入到其中一个位置，使得总扣分最小。

在这个算法中，我们使用了分治法对子问题进行处理，并利用了贪心选择策略和动态规划思想来求解问题。