POJ - 2976 Dropping tests(01分数规划---二分(最大化平均值))

时间：2023-11-26 14:30:26

题意：有n组ai和bi，要求去掉k组，使下式值最大。

POJ - 2976 Dropping tests(01分数规划---二分(最大化平均值))

分析：

1、此题是典型的01分数规划。

01分数规划：给定两个数组，a[i]表示选取i的可以得到的价值，b[i]表示选取i的代价。x[i]=1代表选取i，否则x[i]=0。

求一个选择方案使得所有选择物品的总收益/总代价的值最大或是最小。

即y=Σ(a[i]*x[i])/Σ(b[i]*x[i])取得最值。

2、这类问题可以用二分解决。

最大化平均值：

设某种选取方案后得到的值为Σa[i]/Σb[i]，判断此时二分到的值mid是否符合要求，若Σa[i]/Σb[i] >= mid，则表示题目中的式子

POJ - 2976 Dropping tests(01分数规划---二分(最大化平均值))还可以更大。

而Σa[i]/Σb[i] >= mid，可推出Σ(a[i] - mid * b[i]) >= 0，

即根据mid算出所有的a[i] - mid * b[i]后，从大到小排序，选取前n - k个，如果他们的和>=0,则mid确实符合要求，那么l = mid + eps。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 1000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

double a[MAXN], b[MAXN], w[MAXN];

int n, k;

bool judge(double x){

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

        w[i] = a[i] - x * b[i];

    }

    sort(w, w + n, greater<double>());

    double ans = 0;

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

        ans += w[i];

    }

    return dcmp(ans, 0) >= 0;

}

double solve(){

    double l = 0, r = 1e13;

    double ans = 0;

    while(dcmp(l, r) <= 0){

        double mid = (l + r) / 2;

        if(judge(mid)){

            ans = mid;

            l = mid + eps;

        }

        else{

            r = mid - eps;

        }

    }

    return ans * 100;

}

int main(){

    while(scanf("%d%d", &n, &k) == 2){

        if(!n && !k) return 0;

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

            scanf("%lf", &a[i]);

        }

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

            scanf("%lf", &b[i]);

        }

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

    }

    return 0;

}

　　

相关文章