小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办，而且他要让他花的每一分钱都物超所值，即：买下来的东西的总价值/总花费=max。请你来看看，他会买哪些东西吧。
分数规划，二分答案 有 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; }
