大佬们救命,明天就要考试了
查看原帖
大佬们救命,明天就要考试了
295847
wumingshisdy楼主2021/12/22 21:15

只能过第一个,后面都WA

package nuistOj;


import java.util.Arrays;
import java.util.Scanner;

public class problem1477部分背包问题 {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        double t = scanner.nextDouble();
        double max = 0;
        Coin[] arr = new Coin[n+1];
        for (int i=1;i<=n;i++){
            arr[i] = new Coin();
            arr[i].wei=scanner.nextDouble();
            arr[i].val=scanner.nextDouble();
            arr[i].ever=arr[i].val/arr[i].wei;
        }
        Arrays.sort(arr,1,n+1,(o1, o2) -> (int) (o2.ever-o1.ever));
        for (int i=1;i<=n&&t>0;i++){
           if (t>=arr[i].wei){
               max+=arr[i].val;
               t-=arr[i].wei;
           }else{
               max+=arr[i].ever*t;
               t=0;
           }
        }
        System.out.printf("%.2f\n",max);
    }

    static class Coin {
        double wei;
        double val;
        double ever;
    }
}

2021/12/22 21:15
加载中...