模型：
给定整数 (v_i, c_i)，规定 (x_i=0) 或 (1)，存在一组解 ({x_i})，使得 (displaystyle frac{sum_{i=1}^{n} v_ix_i}{sum_{i=1}^{n} c_ix_i}) 最大。
解法：
最大化 (displaystyle frac{v_i}{c_i})（即性价比）的贪心方法不可行。
(displaystyle frac{sum_{i=1}^{n} v_ix_i}{sum_{i=1}^{n} c_ix_i}ge R) 变式为 (sum_{i=1}^{n} (v_i-Rcdot c_i)x_ige 0)。
二分答案 (R)，对于 (R( ext{mid}))，计算 (sum_{i=1}^{n} (v_i-Rcdot c_i)x_i) 的最大值，若最大值非负，令 (l= ext{mid}) ((R) 偏小)，否则 (r= ext{mid}) ((R) 偏大)。
代码：
（ssoj2388 coffee）
#include <cstdio>
#include <algorithm>
#define db double
#define eps 1e-5
using namespace std;
int n, m;
struct node {
int w, c; db r;
bool operator < (const node& A) const {return r>A.r; }
} G[203];
int main() {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i) scanf("%d", &G[i].w);
for (int i=1; i<=n; ++i) scanf("%d", &G[i].c);
db l=0.0, r=1000.0;
while (l+eps<r) {
db mid=(l+r)/2.0;
for (int i=1; i<=n; ++i) G[i].r=G[i].w-mid*G[i].c;
sort(G+1, G+n+1);
db sum=0.0;
for (int i=1; i<=m; ++i) sum+=G[i].r;
if (sum<0) r=mid; else l=mid;
}
printf("%.3lf
", l);
return 0;
}