小咪买东西（01规划问题）

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int INF = 0x3f3f3f3f;
const int MAX = 1e4 + 7;
int n, k;
int c[MAX], v[MAX];
double w[MAX];
//全局变量区

bool judge(double x) {
    for (int i = 1; i <= n; i++)
        w[i] = v[i] - x * c[i];
    sort(w + 1, w + 1 + n, greater<double>());
    double sm = 0;
    for (int i = 1; i <= k; i++)
        sm += w[i];
    return sm > 0;
}
//函数预定义区

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> c[i] >> v[i];
        double l = 0, r = INF;
        for (int i = 1; i <= 100; i++) {
            double mid = (l + r) / 2;
            if (judge(mid)) l = mid;
            else r = mid;
        }
        cout << (int)r << endl;
    }
    return 0;
}
//函数区

借用他人答案

与二分法思想一致，有答案判断是否合理