小咪买东西

思路分析：
二分+01分数规划。
挑战程序设计竞赛P114-P145有详细的分析，不过多赘述。

Code:

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define MaxN 10010
typedef long long LL;
int C[MaxN],V[MaxN];
double A[MaxN];
int n,k;
bool cmp(double _A,double _B){
    return _A > _B;
}
bool check(double x){  
    for(int i=0; i<n; i++) A[i]=V[i]-x*C[i];
    sort(A,A+n,cmp);;
    double sums=0.0;
    for(int i=0; i<k; i++) sums+=A[i];
    return sums>=0;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while( T-- ){
        cin>>n>>k;
        for(int i=0; i<n; i++) cin>>C[i]>>V[i];//花费 价值
        double _left=0, _right=MaxN;
        for(int i=0; i<100; i++){
            double mid=( _left + _right )/2.0;
            if( check(mid) ) _left=mid;
            else _right=mid;
        }
        printf("%d\n",(int)_left);
    }
    return 0;
}