解题思路:
如题,一个物件有两个属性(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语言代码)浏览:875 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:585 |
简单的a+b (C语言代码)浏览:494 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:869 |
分糖果 (C++代码)浏览:1447 |
WU-拆分位数 (C++代码)浏览:787 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:799 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:567 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:642 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:534 |