poj2976（01分数规划）

poj2976

题意

给出 a b 数组，一共 n 对数，其中最多可以去掉 k 对，问怎样使剩下比率（原始比率是 $ \frac{\sum_{i=1}^{n} a}{\sum_{i=1}^{n} b}*100 $）最大。

分析

设 $l=\frac{\sum a}{\sum b}$，我们要求使得 l 最大，构造新函数 $F()={\sum a}-l*{\sum b}$，设$D()=a-l*b$，显然 F() 是随 l 增大单调递减的，如果对于某个 l 使得 F() > 0 ，

则有 $\frac{\sum a}{\sum b}>l$，那么我们可以知道此时存在比l更优的值（我们要 l 尽可能大）；当 F() = 0 时，这个 l 即为所求值；当 F() < 0 时，无意义，此时的 l 根本取不到。

那么 F() 函数的功能是让我们可以不断逼近答案（即告诉我们后面有更优的值），如果我们现在选定了一个 l ，计算出 D 数组，从大到小选 n - k 个，这样使 F() 最大（F()越大，那么告诉我们后面存在更大的 l ）。可以二分 l 当 F(l) >= 0 时，l = mid，否则，r = mid。

code

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;

const double INF = 1e15;

int n, k;

int a[MAXN], b[MAXN];

double d[MAXN];

int work(double rate) {

    for(int i = 0; i < n; i++) {

        d[i] = a[i] - rate * b[i];

    }

    sort(d, d + n);

    double F = 0;

    for(int i = n - 1; i >= k; i--) {

        F += d[i];

    }

    return F >= 0;

}

double solve() {

    double l = 0, r = 1, mid = 0;

    while(r - l > 1e-5) {

        mid = (l + r) / 2;

        if(work(mid)) l = mid;

        else r = mid;

    }

    return mid * 100;

}

int main() {

    while(cin >> n >> k && (n + k)) {

        for(int i = 0; i < n; i++) {

            cin >> a[i];

        }

        for(int i = 0; i < n; i++) {

            cin >> b[i];

        }

        printf("%.0f\n", solve());

    }

    return 0;

}

巴特西

poj2976（01分数规划）

poj2976

题意

分析

code

最新文章

热门文章