[POJ2976]Dropping tests（01分数规划）

题目描述

传送门
题意：给出ai,bi，选择至少n-k个，使100* ∑ai∑bi 最大

题解

01分数规划裸题…
化一下式子 R=∑ai∑bi ，那么当 di=∑ai−R∗∑bi>0 的时候一定存在更优解
二分R，算出 di ，贪心地选前n-k大，然后判断是否存在更优解就可以了

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 1005

const double eps=1e-4;
int dcmp(double x)
{
    if (x<=eps&&x>=-eps) return 0;
    return (x>0)?1:-1;
}
int n,k;
double a[N],b[N],d[N],ans;

bool check(double mid)
{
    for (int i=1;i<=n;++i) d[i]=a[i]-mid*b[i];
    sort(d+1,d+n+1);
    double now=0;
    for (int i=n;i>k;--i)
        now+=d[i];
    return dcmp(now)>=0;
}
double find()
{
    double l=0.0,r=1.0,mid,ans;
    while (dcmp(r-l)>0)
    {
        mid=(l+r)/2.0;
        if (check(mid)) ans=l=mid;
        else r=mid;
    }
    return ans;
}
int main()
{
    while (~scanf("%d%d",&n,&k))
    {
        if (!n&&!k) break;
        for (int i=1;i<=n;++i) scanf("%lf",&a[i]);
        for (int i=1;i<=n;++i) scanf("%lf",&b[i]);
        ans=100.0*find();
        printf("%.0lf\n",ans);
    }
}