POJ 2976 Dropping tests [01分数规划]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1005;
const double eps=1e-4;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,k;
double a[N],b[N],c[N];
bool check(double mid){
    for(int i=1;i<=n;i++) c[i]=100*a[i]-mid*b[i];
    sort(c+1,c+1+n);
    double sum=0;
    for(int i=1;i<=k;i++) sum+=c[n-i+1];
    return sum>0;
}
void solve(){
    double l=0.0,r=100.0;
    while(r-l>eps){
        double mid=(l+r)/2.0;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.0f
",l);
}
int main(){
    freopen("in","r",stdin);
    while(scanf("%d%d",&n,&k)!=EOF){
        if(n==0&&k==0) break;
        k=n-k;
        for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
        for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
        solve();
    }
}