[POJ3111]K Best（分数规划, 二分）

题目链接：http://poj.org/problem?id=3111

求选k对数，使得上述式子值最大。容易想到设左边为一个值，对式子变形以下，得到sigma(v-r*w))==0的时候就是最大的，<０是最小的。二分这个r就行了。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <cassert>
 8 #include <cstdio>
 9 #include <bitset>
10 #include <vector>
11 #include <deque>
12 #include <queue>
13 #include <stack>
14 #include <ctime>
15 #include <set>
16 #include <map>
17 #include <cmath>
18 using namespace std;
19 
20 typedef struct P {
21     int id;
22     double v;
23 }P;
24 const int maxn = 100100;
25 const double eps = 1e-8;
26 int ret[maxn];
27 int v[maxn], w[maxn];
28 int n, k;
29 P p[maxn];
30 bool cmp(P a, P b) {
31     return a.v > b.v;
32 }
33 
34 bool ok(double r) {
35     for(int i = 0; i < n; i++) {
36         p[i].id = i;
37         p[i].v = v[i] - w[i] * r;
38     }
39     sort(p, p+n, cmp);
40     double s = .0;
41     for(int i = 0; i < k; i++) {
42         s += p[i].v;
43     }
44     return s >= 0;
45 }
46 
47 int main() {
48     // freopen("in", "r", stdin);
49     while(~scanf("%d%d",&n, &k)) {
50         for(int i = 0; i < n; i++) {
51             scanf("%d%d",&v[i], &w[i]);
52         }
53         double lo = .0, hi = 1e7;
54         while(hi - lo > eps) {
55             double mid = (lo + hi) / 2.0;
56             if(ok(mid)) lo = mid;
57             else hi = mid;
58         }
59         for(int i = 0; i < k; i++) {
60             printf("%d%c", p[i].id + 1, i==k-1?'
':' ');
61         }
62     }
63     return 0;
64 }