poj 2976 0 1 分数规划

一脸懵逼   好像是个很高端的东西  0 1 分数规划  其实就是二分一下 不会证明

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>

using namespace std;

#define LL long long
#define MAXN 1010
#define inf  1000000000.0

LL a[MAXN],b[MAXN];
double y[MAXN];
int n,k;
bool test(double x)
{
    for(int i=1;i<=n;i++)
        y[i]=a[i]-b[i]*x;
    sort(y+1,y+n+1);
    double sum=0;
    for(int i=k+1;i<=n;i++)
        sum+=y[i];
    return sum>=0;
}
int main()
{

    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==0&&k==0)
            break;
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%lld",&b[i]);
        double l,r;
        l =0;
        r=1;
        while(r-l>=1e-4)
        {
            double mid=(l+r)/2;
            if(test(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%d
",(int)(l*100+0.5));
    }
    return 0;
}