题目链接

Dropping tests POJ - 2976

思路

$$ 最大化平均值\\\\我们假设一个可行解X, 答案求最大的X，由于具有单调性，可以二分求解\\\\X为可行解的条件为 100 * (\sum_{i = 1}^ka_i/\sum_{i = 1}^kb_i) >= X\\\\整理一下式子：\\\\\sum_{i = 1}^k(100 * a_i - X * b_i) >= 0\\\\因此我们按100 * a_i - X * b_i从大到小排序取前k个就好了 $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e3 + 10;
int n, k;
int a[MAXN], b[MAXN], id[MAXN];
double mid;

bool cmp(int x, int y) {
    return a[x] * 100.0 - mid * b[x] > a[y] * 100.0 - mid * b[y];
}

bool check() {
    for (int i = 1; i <= n; i++) {
        id[i] = i;
    }
    double res = 0;
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= k; i++) {
        int cur = id[i];
        res += a[cur] * 100.0 - mid * b[cur];
    }
    return res >= 0;
}

int main() {
    while (scanf("%d%d", &n, &k), n + k) {
        k = n - k;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);// don't forget &
        }
        double l = 0, r = 100, ans = 0;
        for (int i = 1; i <= 100; i++) {
            mid = (l + r) / 2;
            if (check()) {
                ans = mid;
                l = mid;
            } else {
                r = mid;
            }
        }
        printf("%d\n", (int)(ans + 0.5));
    }

    return 0;
}