wyh的物品 题解

标准的01分数规划
首先二分查找符合条件最大的x，如果符合条件就选取右区间，不符合就查找左区间。
当r-l相差为0.0000001时我们视为r=l，此时可以返回l了。
最主要的是如何去写check函数
首先我们将v[i]-s[i]x存到数组中，因为我们之前假设了v[i]/s[i]=x此时x是最大值。
所以我们只需要找v[i]-s[i]x最大的k项求和即可，如果和大于0符合条件，小于0不符合。
最后大家一定注意精度问题 以及/2.0。

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static int n=0;
    public static int k=0;
    public static double s[];
    public static double v[];
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T = (int)in.nval;
        while(T-->0)
        {
        in.nextToken();
        n = (int)in.nval;
        in.nextToken();
        k = (int)in.nval;
        s = new double[n];
        v = new double[n];
        for(int i=0;i<n;i++)
        {
            in.nextToken();
            s[i] = in.nval;
            in.nextToken();
            v[i] = in.nval;
        }
        double l=0.00001,r=1000000009.0,mid =(l+r)/2.0;
            while(r-l>=0.0000001)
            {
               mid =(l+r)/2.0;
                if(check(mid)==true)
                {
                    l = mid;
                }
                else{
                    r = mid;
                }
            }
            out.println(String.format("%.2f",l));
        }
        out.flush();
    }
    public static boolean check(double x)
    {
        double num[] = new double[n];
        for(int i=0;i<n;i++)
        {
            num[i] = v[i]-x*s[i];
        }
        Arrays.sort(num);
        double ans=0;
        for(int i=n-1;i>n-1-k;i--)
            ans+=num[i];
        if(ans>=0.000001)
            return true;
        else
            return false;
    }
                  }