小咪买东西

题目分析：

1.总价值/总花费=max，设总价值为b,总花费为a,答案为未知：b/a = x
2. 对x进行二分处理（取值范围（0，inf））
3. 取k个物品，那么进行排序取（bi/ai)前k个最大的

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define eps 1e-6

const int N = 1e4 + 10;

int t;
int n,m;

struct Node{
    double a,b,c;
}node[N];

bool cmp(Node a,Node b){
    return a.c > b.c;    
} 

bool check(double x){
    for(int i = 1; i <= n; i ++ ){
        node[i].c = node[i].b - node[i].a * x;
    }
    sort(node + 1, node + n + 1,cmp);
    double ans = 0;
    for(int i = 1; i <= m; i ++){
        ans += node[i].c;
    }
    return ans >= 0;
}

int main() {
    cin >> t;
    while(t -- ){
        cin >> n >> m;
        for(int i = 1; i <= n; i ++ ){
            double a,b; cin >> a >> b;
            node[i] = {a,b};
        }
        double l = 0,r = inf;
        while(r - l > eps){
            double mid = (l + r) / 2.0;
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%d\n",(int)(l + eps));
    }    
    return 0;
}