小明上学,老师布置了 n 个作业,每个作业恰好需要一天做完,每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3,每个作业的最后提交时间t = [1,3,1],作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束,请给出小明做作业的顺序,以便扣最少的分数。通过Java语言用贪心算法实现上述问题代码
时间: 2024-02-25 17:53:53 浏览: 20
以下是Java语言实现上述问题的贪心算法代码:
```
import java.util.*;
public class Main {
static class Homework implements Comparable<Homework> {
int t; // 最后提交时间
int k; // 逾期扣分
public Homework(int t, int k) {
this.t = t;
this.k = k;
}
// 比较器:按照逾期扣分从大到小排序
public int compareTo(Homework h) {
return h.k - this.k;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
int n = sc.nextInt();
if (n == 0) {
break;
}
Homework[] works = new Homework[n];
for (int i = 0; i < n; i++) {
int t = sc.nextInt();
int k = sc.nextInt();
works[i] = new Homework(t, k);
}
Arrays.sort(works); // 按照逾期扣分从大到小排序
int day = 0; // 当前可以做作业的天数
int score = 0; // 总扣分
for (int i = 0; i < n; i++) {
day += works[i].t; // 当前作业的最后提交时间
score += works[i].k * Math.max(day - works[i].t, 0); // 计算扣分
}
System.out.println(score);
}
}
}
```
代码的核心思路是将作业按照逾期扣分从大到小排序,然后依次做作业,计算总扣分。具体实现细节见代码注释。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)