小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。通过贪心算法用Java语言实现代码
时间: 2024-02-22 11:59:20 浏览: 16
以下是使用贪心算法求解该问题的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[][] homework = new int[n][2];
for (int i = 0; i < n; i++) {
homework[i][0] = t[i];
homework[i][1] = k[i];
}
Arrays.sort(homework, Comparator.comparingInt(o -> o[0]));
// 计算最小扣分数
int minScore = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += homework[i][0]; // 累计时间
minScore += homework[i][1] * sum; // 累计扣分数
}
System.out.println(minScore);
}
}
}
```
运行程序后,输入以下数据进行测试:
```
3
1 6
3 2
1 3
0
```
程序会输出最小扣分数为4,结果与分治算法的结果一致。