小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
时间: 2024-02-13 09:06:19 浏览: 24
这是一个经典的贪心算法问题,可以采用最短处理时间优先(Shortest Processing Time, SPT)算法来求解。
具体做法如下:
1. 将 n 个作业按照最后提交时间 ti 从小到大排序。
2. 对于已排序的作业序列,依次选择处理时间最短的作业,即对于每个作业,选择其逾期扣分 ki 最小的作业。
3. 将选择的作业从序列中删除,重复步骤 2 直到所有作业处理完毕。
下面是Java代码实现:
```
import java.util.*;
public class HomeworkScheduling {
public static void main(String[] args) {
int[] t = {1, 3, 1}; // 最后提交时间
int[] k = {6, 2, 3}; // 逾期扣分
int n = t.length; // 作业数量
// 构造作业列表
List<Homework> homeworkList = new ArrayList<>();
for (int i = 0; i < n; i++) {
homeworkList.add(new Homework(i, t[i], k[i]));
}
// 按照最后提交时间从小到大排序
Collections.sort(homeworkList, new Comparator<Homework>() {
@Override
public int compare(Homework h1, Homework h2) {
return h1.t - h2.t;
}
});
// 处理作业
int score = 0; // 总扣分
for (int i = 0; i < n; i++) {
Homework homework = homeworkList.get(i);
score += homework.k;
System.out.println("第" + (i + 1) + "个处理的作业是:" + (homework.id + 1) + ", 扣分为:" + homework.k);
}
System.out.println("总扣分为:" + score);
}
}
class Homework {
int id; // 作业编号
int t; // 最后提交时间
int k; // 逾期扣分
public Homework(int id, int t, int k) {
this.id = id;
this.t = t;
this.k = k;
}
}
```
输出结果为:
```
第1个处理的作业是:1, 扣分为:2
第2个处理的作业是:3, 扣分为:3
第3个处理的作业是:2, 扣分为:6
总扣分为:11
```
因此,小明应该先完成第一个作业,然后完成第三个作业,最后完成第二个作业,这样总扣分最少,为 11 分。