POJ2976 Dropping tests 01分数规划

裸题

看分析请戳这里：http://blog.csdn.net/hhaile/article/details/8883652

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=1e3+5;
const double eps=1e-7;
int n,k;
double a[N],b[N],c[N];
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]);
       double l=0.0,r=1.0,mid;
       while(r-l>eps){
        mid=(l+r)/2;
        for(int i=1;i<=n;++i)
          c[i]=a[i]-mid*b[i];
        sort(c+1,c+1+n);
        double sum=0;
        for(int i=k+1;i<=n;++i)
          sum+=c[i];
        if(sum>0)l=mid;
        else r=mid;
       }
       printf("%.0f
",mid*100);
    }
    return 0;
}