小咪买东西 分数规划

分数规划，二分答案
有 n 个物品，有属性值 ai,bi要求选出至多 k 个物品，使得sum(ai) / sum(bi)尽可能大。
我们要首先二分答案 x，若 sum(ai) / sum(bi) ≥x 则说明答案可以更大。
稍微变形一下：sum(a[i]) >= sum(b[i]) * x;
继续：sum(a[i] - b[i] * x) >= 0
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
typedef long long ll;
ll a[maxn], b[maxn], c[maxn];
int n, k;
bool cmp(ll a, ll b) {
    return a > b;
}
int check(int x) {
    for (int i = 1; i <= n; i++) {
        c[i] = b[i] - a[i] * x;
    }
    sort (c + 1, c + n + 1, cmp);
    ll ans = 0;
    for (int i = 1; i <= k; i++) { //取最大的k个
        ans += c[i];
    }
    return ans >= 0; //判断 sum(b[i] - a[i] * x) >=0 -> 答案l = mid + 1  else r = mid - 1
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        int l = 0, r = 10000;
        for (int i = 1; i <= n; i++) {
            cin >> a[i] >> b[i];;
        }
        while (l <= r) { //二分答案
            int mid = (l + r) / 2;
            if (check(mid)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << l - 1 << endl;
    }
    return 0;
}