模型：

给定整数 \(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-R\cdot c_i)x_i\ge 0\)。

二分答案 \(R\)，对于 \(R(\text{mid})\)，计算 \(\sum_{i=1}^{n} (v_i-R\cdot c_i)x_i\) 的最大值，若最大值非负，令 \(l=\text{mid}\) (\(R\) 偏小)，否则 \(r=\text{mid}\) (\(R\) 偏大)。

代码：

（ssoj2388 coffee）

#include 
    
     #include 
     
      #define db double#define eps 1e-5using 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