小咪买东西 题解

二分查找符合条件的x的最大值
最后返回l-1即为答案
check和之前的wyh的物品那个题一样没啥区别

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;
        }
        int l=0,r=1000000009,mid =(l+r)/2;
            while(l<=r)
            {
               mid =(l+r)/2;
                if(check(mid)==true)
                {
                    l = mid+1;
                }
                else{
                    r = mid-1;
                }
            }
            out.println(l-1);
        }
        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)
            return true;
        else
            return false;
    }
                  }