nyoj914(二分搜索+贪心)
题目意思:
pid=914">acm.nyist.net/JudgeOnline/problem.php?pid=914
如今有n个物品的重量和价值各自是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价值最大吗?
- 输入
- 有多组測试数据
每组測试数据第一行有两个数n和k。接下来一行有n个数Wi和Vi。
(1<=k=n<=10000) (1<=Wi,Vi<=1000000) - 输出
- 输出使得单位价值的最大值。(保留两位小数)
- 例子输入
-
3 2
2 2
5 3
2 1 - 例子输出
-
0.75
题目分析:
此题直接对单位价格进行贪心会出现故障,并且不难从例子上看出来。因为k个物品的单位价格一定不大于最大单位价格的物品,
并且一定会大于0,因此能够用二分搜素+贪心来解题。
详细细节见凝视
AC代码:
/**
*贪心+二分搜索
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define exp 1e-5
using namespace std;
typedef struct node{
double w,v;
}node;
node p[10005];
double y[10005];
int n,k;
int cmp(double a,double b){
if(a>b) return 1;
return 0;
}
int Judge(double x){//二分搜索最大的且最恰当的值是否合理。if(合理)证明还有继续加大的空间,能够继续增大
for(int i=0;i<n;i++){
y[i]=p[i].v-p[i].w*x;
}
sort(y,y+n,cmp);
double s=0;
for(int i=0;i<k;i++){
s+=y[i];
}
if(s>=0) return 1;
else return 0;
}
double Search(double ma){
double l=0,r=ma;
while(r-l>exp){
double mid=(l+r)/2;
if(Judge(mid)){//当前值还小,还要增大
l=mid;
}
else{//当前值大了,须要减小
r=mid;
}
}
return l;//或者return r;此时l=r
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF){
double ma=0;//k个最大平均值一定小于等于单个最大价值且大于0
for(int i=0;i<n;i++){
scanf("%lf%lf",&p[i].w,&p[i].v);
if(ma<p[i].v/p[i].w) ma=p[i].v/p[i].w;
}
printf("%.2lf\n",Search(ma));
}
return 0;
}
最新文章
- Linux system 函数的一些注意事项
- Solved Unable to copy the source file ./installer/services.sh to the destination file /etc/vmware-t
- tcpdump常用命令
- enter 默认搜索
- VS 2013--工程的创建,scanf报错,常用快捷键,行号设置
- 为Ghost博客扩展代码高亮、数学公式、页面统计、评论
- 2018 Multi-University Training Contest 1
- re正则匹配
- recovery log直接输出到串口
- Linux下 XordDos(BillGates)木马查杀记录
- OI回忆录第一章 逐梦之始
- [hadoop读书笔记] 第一章 初识 Hadoop
- Ubuntu下MySQL数据库文件 物理迁移后 出现的问题
- 浏览器根对象window之窗体和工具条
- 小数据池,bytes
- ICLR 2014 International Conference on Learning Representations深度学习论文papers
- python 网络请求类库 requests 使用
- python3网络爬虫系统学习:第二讲 基本库requests(一)
- lintcode-167-链表求和
- 编写简单的spring mvc程序,在tomcat上部署
热门文章
- com.alibaba.fastjson.JSONPathException: expect &#39;], but &#39;y&#39;
- ACdream 1127(Base Station-树状数组-2个约束条件)
- ABAP FIELD-SYMBOLS 有大作用- 将没有可改參数的增强出口变得也能改主程序的值了
- MAVEN创建并打包web项目
- Ubuntu 16.04 安装 Open Jdk
- ubuntu12.04下NFS链接开发板并测试交叉编译的第一个应用
- 报表工具Report Builder 3.0的安装
- 常用css框架 Sass/Less
- label标签的可访问性问题
- 关于Spring的69个面试问答——终极列表 (转)