博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
nyist 914
阅读量:5110 次
发布时间:2019-06-13

本文共 825 字,大约阅读时间需要 2 分钟。

#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;
}

/*

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

*/

转载于:https://www.cnblogs.com/huaixiaohai2015/p/5184729.html

你可能感兴趣的文章
万能的SQLHelper帮助类
查看>>
tmux的简单快捷键
查看>>
[Swift]LeetCode922.按奇偶排序数组 II | Sort Array By Parity II
查看>>
Html5 离线页面缓存
查看>>
《绿色·精简·性感·迷你版》易语言,小到不可想象
查看>>
Android打包key密码丢失找回
查看>>
VC6.0调试技巧(一)(转)
查看>>
类库与框架,强类型与弱类型的闲聊
查看>>
webView添加头视图
查看>>
php match_model的简单使用
查看>>
在NT中直接访问物理内存
查看>>
Intel HEX 文件格式
查看>>
SIP服务器性能测试工具SIPp使用指导(转)
查看>>
php_扑克类
查看>>
回调没用,加上iframe提交表单
查看>>
(安卓)一般安卓开始界面 Loding 跳转 实例 ---亲测!
查看>>
Mysql 索引优化 - 1
查看>>
LeetCode(3) || Median of Two Sorted Arrays
查看>>
大话文本检测经典模型:EAST
查看>>
待整理
查看>>