题解 | #小咪买东西#

01分数规划

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i = 0;i<T;i++){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int []c = new int[n];
            int []v = new int[n];
            double []resultset = new double[n];
            for(int j = 0;j<n;j++){
                c[j] = sc.nextInt();
                v[j] = sc.nextInt();
                resultset[j] = v[j]*1.0/c[j];
            }
            Arrays.sort(resultset);
        
        int start = 0;
        int end = 1000000009;
        int mid = (start+end)/2;
        while(end>=start){
            if(check(c,v,mid,k)){
                start = mid+1;
                mid = (start+end)/2;
                }else{
                    end = mid-1;
                    mid = (start+end)/2;
                }
        }
        System.out.println(end);
    }
    }

    public static boolean check(int []c,int []v,double mid,int k){
        int len = c.length;
        double []paixu = new double[len];
        for(int i =0;i<len;i++){
            paixu[i] = v[i]-c[i]*mid;
        }
        Arrays.sort(paixu);
        int sum = 0;
        for(int i = 0;i<k;i++){
            sum+=paixu[len-i-1];
        }
        if(sum>=0) return true;
        return false;
    }
}