02、写作业问题 小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。
时间: 2024-02-18 07:05:30 浏览: 71
这道题目可以使用贪心算法来解决。
首先,将每个作业的最后提交时间和逾期扣分按照最后提交时间的先后顺序进行排序,如果最后提交时间相同,则按照逾期扣分从小到大排序。
然后,按照排序后的顺序,依次安排小明做作业。如果小明的时间还没有超过最后提交时间,则直接做作业,否则扣除逾期扣分。
下面是Java代码实现:
```java
import java.util.*;
public class Homework {
static class Job {
int time; // 最后提交时间
int penalty; // 逾期扣分
public Job(int time, int penalty) {
this.time = time;
this.penalty = penalty;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<Job> jobs = new ArrayList<>();
while (true) {
int n = sc.nextInt();
if (n == 0) break;
int[] time = new int[n];
int[] penalty = new int[n];
for (int i = 0; i < n; i++) {
time[i] = sc.nextInt();
penalty[i] = sc.nextInt();
}
// 将作业按照最后提交时间和逾期扣分排序
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (time[i] > time[j] || (time[i] == time[j] && penalty[i] > penalty[j])) {
int temp = time[i];
time[i] = time[j];
time[j] = temp;
temp = penalty[i];
penalty[i] = penalty[j];
penalty[j] = temp;
}
}
}
// 安排小明做作业
int currentTime = 0; // 当前时间
int totalPenalty = 0; // 总扣分
for (int i = 0; i < n; i++) {
if (currentTime + 1 <= time[i]) { // 没有逾期
currentTime++;
} else { // 逾期了
totalPenalty += penalty[i];
}
}
jobs.add(new Job(currentTime, totalPenalty));
}
// 输出结果
for (Job job : jobs) {
System.out.println(job.penalty);
}
}
}
```
注意:上述代码中,时间和逾期扣分是分别存储在两个数组中的,可以使用一个数组或者一个二维数组来存储作业的信息,根据实际情况进行修改。同时,在对作业进行排序时,可以使用Java内置的排序函数,更加方便。
阅读全文