nyist 914

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int w[10005],v[10005];
int n,k;
double maxu,c[10005];
const double ex=0.000001;

bool Check(double x){//若是选定当前单位价值的结果是可以或者不可以

for(int i=0;i<n;i++)
c[i]=v[i]-x*w[i];
sort(c,c+n);
double sum=0;
for(int i=0;i<k;i++)//判定当前单位价值时，是不是比较好的选择，>=0为好，则可能有更优的情况
sum+=c[n-1-i];
return sum>=0;
}

double ans(double x){

double fir=0,las=x,mid;
while(fabs(fir-las)>ex){
mid=(fir+las)/2.0;
if(Check(mid))//若是当前单位价值都满足，则最终结果不会低于当前单位价值
fir=mid;
else
las=mid;
}
return fir;
}

int main(){

while(scanf("%d%d",&n,&k)==2){
maxu=-1;
for(int i=0;i<n;i++){
scanf("%d%d",&w[i],&v[i]);
if(v[i]*1.0/w[i]>maxu)//确定单位价值的上限值
maxu=v[i]*1.0/w[i];
}
printf("%.2lf\n",ans(maxu));
}
return 0;
}

/*

二分确定单位价值的范围，贪心用来确定是否会出现更优解

*/

nyist 914

原文：http://www.cnblogs.com/huaixiaohai2015/p/5184729.html