小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数,Java代码实现
时间: 2024-02-22 17:56:45 浏览: 145
好的,以下是Java代码实现:
```java
import java.util.*;
public class Homework {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n;
do {
System.out.print("请输入作业数量:");
n = scanner.nextInt();
if (n == 0) {
break;
}
int[] t = new int[n];
int[] k = new int[n];
for (int i = 0; i < n; i++) {
System.out.print("请输入第" + (i + 1) + "个作业的最后提交时间:");
t[i] = scanner.nextInt();
System.out.print("请输入第" + (i + 1) + "个作业的逾期扣分:");
k[i] = scanner.nextInt();
}
int[] order = selectOrder(n, t, k);
System.out.println("小明做作业的顺序为:" + Arrays.toString(order));
} while (n != 0);
}
private static int[] selectOrder(int n, int[] t, int[] k) {
int[] order = new int[n];
boolean[] selected = new boolean[n];
for (int i = 0; i < n; i++) {
int maxK = -1;
int maxT = -1;
int maxIndex = -1;
for (int j = 0; j < n; j++) {
if (!selected[j]) {
if (k[j] > maxK || (k[j] == maxK && t[j] > maxT)) {
maxK = k[j];
maxT = t[j];
maxIndex = j;
}
}
}
order[i] = maxIndex + 1;
selected[maxIndex] = true;
}
return order;
}
}
```
其中,`selectOrder`方法实现了贪心算法,首先初始化一个空的作业顺序数组`order`和一个全部为`false`的选择数组`selected`,然后依次选择每个作业,每次选择当前未选择的逾期扣分最大且最后提交时间最近的作业,将其加入作业顺序数组中,并将其对应的选择数组中的值设为`true`,直至所有作业都被选择完毕,最终返回作业顺序数组即可。
希望这份Java代码实现能够帮助到你。
阅读全文