解题思路:
如题,一个物件有两个属性(pi质量,gi价值)这时就可以考虑使用咱们java的面向对象的思想了,先创建一个Node对象,为了后续排序和贪心算法的方便,添加一个di属性用来表示物件的价值比(pi/gi).
注意事项:
因为排序需要使用集合里面的sort(Comparator<? super E> c)方法,然后自定义排序方法:
public int compare(Node o1, Node o2) { if (o1.di == o2.di) { return 0; }else { return o1.di<o2.di?1:-1; } }
参考代码:
mport java.util.ArrayList; import java.util.Comparator; import java.util.Scanner; public class 快乐司机1917 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ArrayList<Node> list = new ArrayList<>(); double sum=0;//总价值 int page=0;//当前总质量 while (scanner.hasNextInt()) { int n = scanner.nextInt();//可选物件个数 int max = scanner.nextInt();//载货量 for (int i = 0; i < n; i++) { Node node = new Node(scanner.nextInt(), scanner.nextInt()); list.add(node);//加入集合 } list.sort(new Comparator<Node>() {//重写comparator函数,使其按照自定义的模式去排序 @Override public int compare(Node o1, Node o2) { if (o1.di == o2.di) { return 0; }else { return o1.di<o2.di?1:-1; } } }); for (int i = 0; i <list.size() ; i++) { Node node = list.get(i); if (page + node.gi <= max) {//当容量能容纳此物件时 page+=node.gi;//当前容量增加 sum+=node.pi;//当总价值 }else { sum+=(max-page)*node.di;//当当前容量无法容纳时 如 当前题的最大容量是36 但是 物件的容量超过时 break; } } System.out.printf("%.1f",sum);//进行格式输出 } } } class Node{ int gi;//物品的质量 int pi;//物品的价值 double di;//物品的价值比 public Node(int gi,int pi) { this.gi = gi; this.pi=pi; this.di=1.0*pi/gi; } }
0.0分
1 人评分
C语言训练-排序问题<2> (C++代码)(sort函数)浏览:1573 |
C语言训练-斐波纳契数列 (C语言代码)浏览:1167 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:619 |
简单的a+b (C语言代码)浏览:669 |
兰顿蚂蚁 (C++代码)浏览:1091 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:543 |
回文串 (C语言代码)浏览:2849 |
多输入输出练习1 (C语言代码)浏览:1179 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:666 |
上车人数 (C语言代码)浏览:777 |