模型:
给定整数 \(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 <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\n", l);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3013780.html