poj2976 Dropping tests

思路：

二分最大化平均值，注意结果要四舍五入。

实现：

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 const int MAXN = 1005;
 5 const int INF = 0x3f3f3f3f;
 6 int a[MAXN], b[MAXN], n, k;
 7 double buf[MAXN];
 8 bool check(double m)
 9 {
10     for (int i = 0; i < n; i++) buf[i] = a[i] - m * b[i];
11     sort(buf, buf + n);
12     double sum = 0;
13     for (int i = n - 1; i >= k; i--)
14         sum += buf[i];
15     return sum >= 0;
16 }
17 int main()
18 {
19     while (scanf("%d %d", &n, &k), n || k)
20     {
21         for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
22         for (int i = 0; i < n; i++)    scanf("%d", &b[i]);
23         double l = 0, r = 100, ans = 0;
24         for (int i = 0; i < 100; i++)
25         {
26             double m = (l + r) / 2;
27             if (check(m)) { ans = m; l = m; }
28             else r = m;
29         }
30         printf("%d
", (int)(ans * 100 + 0.5));
31     }
32     return 0;
33 }