POJ 2976 Dropping tests【0/1分数规划模板】

传送门：http://poj.org/problem?id=2976

题意：给出组和，去掉对数据，使得的总和除以的总和最大。

思路：0/1分数规划

设，则（其中等于0或1）

开始假设使得上式成立，将从大到小排序，只取前个(这样一定是最优的)，若所得和大于0，则表示偏小，反之偏大。

代码：

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

const double eps = 1e-7;

int a[1005];

int b[1005];

double s[1005];

int n, k;

double solve(double x)

{

    for(int i = 1; i <= n; i++)

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

    sort(s + 1, s + 1 + n);

    double sum = 0;

    for(int i = k + 1; i <= n; i++)

        sum += s[i];

    return sum;

}

int main()

{

    while(~scanf("%d%d", &n, &k) && (n + k))

    {

        for(int i = 1; i <= n; i++)

        {

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

        }

        for(int i = 1; i <= n; i++)

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

        double l = 0, r = 1;

        double mid ;

        while((r - l) > eps)

        {

            mid = (l + r) / 2;

            if(solve(mid) > 0)

            {

                l = mid;

            }

            else

            {

                r = mid;

            }

        }

        printf("%0.lf\n", mid * 100 );

    }

    return 0;

}