poj3111 K Best

思路：
二分最大化平均值。
迭代次数太多会超时。
实现：
 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 const int MAXN = 100005;
 5 const int INF = 0x3f3f3f3f;
 6 int v[MAXN], w[MAXN], ans[MAXN], n, k;
 7 struct node
 8 {
 9     int id;
10     double x;
11 };
12 node buf[MAXN];
13 bool cmp(const node & a, const node & b)
14 {
15     return a.x < b.x;
16 }
17 bool check(double x)
18 {
19     for (int i = 0; i < n; i++) { buf[i].x = v[i] - x * w[i]; buf[i].id = i; }
20     sort(buf, buf + n, cmp);
21     double sum = 0;
22     for (int i = n - 1; i > n - 1 - k; i--) sum += buf[i].x;
23     if (sum >= 0)
24     {
25         for (int i = n - 1; i > n - 1 - k; i--) ans[n - 1 - i] = buf[i].id; return true;
26     }
27     return false;
28 }
29 int main()
30 {
31     scanf("%d %d", &n, &k);
32     for (int i = 0; i < n; i++) scanf("%d %d", &v[i], &w[i]);
33     double l = 0, r = INF;
34     for (int i = 0; i < 50; i++)
35     {
36         double m = (l + r) / 2;
37         if (check(m)) l = m;
38         else r = m;
39     }
40     for (int i = 0; i < k; i++) printf("%d ", ans[i] + 1);
41     return 0;
42 }