POJ 2976 Dropping tests

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

 

实现代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=10000;
const double eps=1e-8;
double a[MAXN],b[MAXN],d[MAXN];
int N,K;

int cal(double r){
    double sum=0;
    for(int i=0;i<N;i++)
        d[i]=a[i]-r*b[i];
    sort(d,d+N);
    for(int i=K;i<N;i++)
        sum+=d[i];
    if(sum<0)
        return true;
    else
        return false;
}

int main(){
    while(scanf("%d%d",&N,&K)&&(N+K)){
        for(int i=0;i<N;i++)
            scanf("%lf",&a[i]);
        for(int i=0;i<N;i++)
            scanf("%lf",&b[i]);
        double l=0.0,r=1.0;
        while(r-l>eps){
            double mid=(l+r)/2.0;
            if(cal(mid))
                r=mid;
            else l=mid;
        }
        printf("%.0f
",l*100);
    }

}