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

以下是使用分治法求解该问题的Java代码：

import java.util.*;

public class Homework {
    static int[] t; // 最后提交时间数组
    static int[] k; // 逾期扣分数组

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt(); // 作业数量
            if (n == 0) break; // 输入为0时结束程序

            t = new int[n];
            k = new int[n];

            // 输入每个作业的最后提交时间和逾期扣分
            for (int i = 0; i < n; i++) {
                t[i] = scanner.nextInt();
                k[i] = scanner.nextInt();
            }

            // 计算最小扣分数
            int minScore = getMinScore(0, n - 1);
            System.out.println(minScore);
        }
    }

    /**
     * 分治法求解最小扣分数
     * @param left 左边界
     * @param right 右边界
     * @return 最小扣分数
     */
    static int getMinScore(int left, int right) {
        if (left == right) {
            // 只有一个作业时直接返回它的逾期扣分
            return k[left];
        } else {
            int mid = (left + right) / 2;
            int leftMinScore = getMinScore(left, mid); // 左半部分最小扣分数
            int rightMinScore = getMinScore(mid + 1, right); // 右半部分最小扣分数
            int minScore = Math.min(leftMinScore, rightMinScore); // 左右最小扣分数的较小值

            // 计算跨越左右两部分的最小扣分数
            int minLeft = Integer.MAX_VALUE;
            int minRight = Integer.MAX_VALUE;
            int sumLeft = 0;
            int sumRight = 0;
            for (int i = mid; i >= left; i--) {
                sumLeft += t[i];
                if (sumLeft > minScore) break; // 如果当前累计时间已经大于最小扣分数，则退出循环
                minLeft = Math.min(minLeft, k[i]); // 更新左侧最小扣分数
            }
            for (int i = mid + 1; i <= right; i++) {
                sumRight += t[i];
                if (sumRight > minScore) break; // 如果当前累计时间已经大于最小扣分数，则退出循环
                minRight = Math.min(minRight, k[i]); // 更新右侧最小扣分数
            }
            int crossMinScore = minLeft + minRight; // 跨越左右两部分的最小扣分数

            // 返回三个最小扣分数中的最小值
            return Math.min(minScore, crossMinScore);
        }
    }
}

运行程序后，输入以下数据进行测试：

3
1 6
3 2
1 3
0

程序会输出最小扣分数为4。