链接：http://poj.org/problem?id=2976

这是道01分数规划的入门题．给你 n 个数 a_i，b_i，让你从中取出 n – k 对 a_i，b_i，使 \\frac{\\sum{a}}{\\sum{b}} 的值最大．

令 \\lambda=\\frac{\\sum{a}}{\\sum{b}}，则题目就是求\\lambda的最大值，变形就有 \\sum{a}-\\lambda\\sum{b}=0．

令g(\\lambda)=\\max(\\sum{a}-\\lambda\\sum{b})=\\max(\\sum{(a-\\lambda b}))，可证g(\\lambda)是个单调递增函数．

而当 g(\\lambda)=0时，可取得 \\lambda的最大值，所以只需二分\\lambda的值，代入即可．

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double eps = 1e-7;
const int N = 1005;
int n, k;
double mid;
struct node {
    int a, b;
    bool operator < (const node &op) const {
        return 1.0 * (a - mid * b) > 1.0 * (op.a - mid * op.b);
    }
} e[N];
int main()
{
    while (~scanf("%d %d", &n, &k) && (n + k)) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &e[i].a);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &e[i].b);
        }
        double low = 0.0, high = 1.0;
        double ans = 0;
        while (high - low > eps) {
            mid = (low + high) / 2;
            sort(e, e + n);
            long long suma = 0, sumb = 0;
            for (int i = 0; i < n - k; i++) {
                suma += e[i].a;
                sumb += e[i].b;
            }
            double tmp = 1.0 * suma - mid * sumb;
            ans = 1.0 * suma / sumb;
            if (tmp < 0) {
                high = mid;
            } else {
                low = mid;
            }
        }
        printf("%.f\n", ans * 100);
    }
    return 0;
}