OIer博客

题目大意：n个物品，价值是a，价格是b，选出m个，性价比最高是多少？

n个物品，第i个物品价值是$a_i$，费用是$b_i$，购买m个，性价比（$\sum{a_i} / \sum{b_i}$）最大是多少？

解题思路

二分猜答案，假设最佳答案是M，我们猜的是m，那么对于选了的物品，$M = \sum{a_i} / \sum{b_i}$，如果猜的m小了，那么M >= m，即$\sum{a_i} / \sum{b_i} >= m$，也就是$\sum{a_i} – m * \sum{b_i} >= 0$，在已知“答案”的情况下，我们可以直接贪心选择$a_i – m*b_i$最大的物品，如果选k个后非负，那么答案猜小了，或许可以更大；如果是负数，那么猜大了，答案要更小一点。

程序实现

Dinkelbach算法：迭代猜答案。从最小的答案x=0/y=1开始猜，如果猜小了，那么$\sum{a_i} / \sum{b_i} > x/y$，我们继续猜$\sum{a_i} / \sum{b_i}$，这样能比较快的猜出答案，猜不到更大的就停止循环。