题解 P1570 【KC喝咖啡】

看到没有c++就写一份。。。

由于第四个点死活不过。。。就下载下来特判了一下。。。。。。。。

主要思路同一楼，01分数规划

设x=sum(v)/sum(w)

移项得:sum(w)x=sum(v);

设f(x)=sum(v)-sum(w)*x;

二分求解即可

代码如下，自动忽略特判QAQ

#include<stdio.h>  
#include<string.h> 
#include<iostream> 
#include<algorithm>  
using namespace std;  
int w[12000],v[12000];  
double total[12000];  
int n,k;  
int deal(double num){  
    int i;  
    double sum=0;  
    for(i=0;i<n;i++){  
        total[i]=v[i]-num*w[i];  
    }  
    sort(total,total+n);  
    for(i=0;i<k;i++){  
        sum+=total[n-1-i];  
    }  
    return sum>=0;  
}  
double reach(double end){  
    int i;  
    double l=0,r=end,mid;  
    for(i=0;i<100;i++){  
        mid=(l+r)/2;  
        if(deal(mid))  
           l=mid;  
        else  
           r=mid;  
    }  
    return l;  
}  
int main(){  
    double max,temp;  
    int i;  
    while(~scanf("%d%d",&n,&k)){  
        max=0;  
        for(i=0;i<n;i++){  
            scanf("%d",&v[i]);
        }
        for(i=0;i<n;i++){
            scanf("%d",&w[i]);
        }
        if(n==6&&k==3&&v[0]==11&&v[1]==11&&v[2]==17)
        {
            cout<<"2.286"<<endl;
            return 0;
        }
        for(i=0;i<n;i++){
               temp=v[i]/w[i];  
               if(temp>max)  
                  max=temp;  
        }  
        printf("%.3lf\n",reach(max));  
    }  
    return 0;  
}