Youth的最大化
时间限制:1000 ms | 内存限制:65535 KB
难度:4
描述
Yougth现在有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且小于单个物品的最大单位价值。求出单个物品的最大单位价值,然后二分查找即可。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define imax(x,y) (x>y?x:y)
#define MAXN 10005
int n, k;
double w[MAXN], v[MAXN];
int i;
double need[MAXN];
int compare(const void * p1, const void * p2) {
return *(double *)p1 < *(double *)p2 ? : -;
}
bool judge(double x) {
// 算出当前物品达到均值x的代价,
//负数表示比均值小,正数反之
for (i = ; i < n; i++) {
need[i] = v[i] - x*w[i];
} //将need数组从大到小排序
qsort(need, n, sizeof(need[]), compare); // 取前k个,算出它们所需代价之和
// 若为正,则代表超过均值,代表均值不够大,向右区间查找;为负反之
double all_need = ;
for (i = ; i < k; i++) {
all_need += need[i];
}
return all_need >= ? true : false;
}
double binary_search(double right) {
double left = ;
while (right - left > 0.00001) {
double mid = (left + right) / ;
if (judge(mid))
left = mid;
else
right = mid;
}
return left;
}
int main(void)
{
while (scanf("%d %d", &n, &k)!=EOF) {
double max_ratio = ;
for (i = ; i < n; i++) {
scanf("%lf %lf", &w[i], &v[i]);
max_ratio = imax(max_ratio,(v[i]/w[i]));
}
//printf("%lf\n", max_ratio);
double res = binary_search(max_ratio);
printf("%.2lf\n", res);
}
return ;
}
NYOJ-914 Youth的最大化(贪心)的更多相关文章
-
NYOJ 914 Yougth的最大化
Yougth的最大化 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描写叙述 Yougth如今有n个物品的重量和价值各自是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价 ...
-
NYOJ 914 Yougth的最大化【二分/最大化平均值模板/01分数规划】
914-Yougth的最大化 内存限制:64MB 时间限制:1000ms 特判: No 通过数:3 提交数:4 难度:4 题目描述: Yougth现在有n个物品的重量和价值分别是Wi和Vi,你能帮他从 ...
-
NYOJ 1107 最高的奖励(贪心+优先队列)
最高的奖励 时间限制:1000 ms | 内存限制:65535 KB 难度:3 描述 请问:挖掘机技术哪家强?AC了告诉你! 给你N(N<=3*10^4)个任务,每个任务有一个截止完成时 ...
-
nyoj 47——过河问题——————【贪心】
过河问题 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描述 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的 ...
-
NYIST 914 Yougth的最大化
Yougth的最大化时间限制:1000 ms | 内存限制:65535 KB难度:4 描述 Yougth现在有n个物品的重量和价值分别是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价值最大吗? ...
-
nyoj 208 + poj 1456 Supermarket (贪心)
Supermarket 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描述 A supermarket has a set Prod of products on sal ...
-
nyoj 14-会场安排问题 (贪心)
14-会场安排问题 内存限制:64MB 时间限制:3000ms Special Judge: No accepted:9 submit:15 题目描述: 学校的小礼堂每天都会有许多活动,有时间这些活动 ...
-
nyoj 448 寻找最大数(贪心专题)
寻找最大数 时间限制:1000 ms | 内存限制:65535 KB 难度:2 描述 请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大, 比如当n=920813467185 ...
-
nyoj 91 阶乘之和(贪心)
阶乘之和 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 给你一个非负数整数n,判断n是不是一些数(这些数不允许重复使用,且为正数)的阶乘之和,如9=1!+2!+3! ...
随机推荐
-
easyui DataGrid 工具类之 TableUtil class
import java.lang.reflect.InvocationTargetException;import java.util.ArrayList;import java.util.HashM ...
-
聊聊 #pragma 和 // MARK:
我去,就这两个东西还要讲?是OC或Swift开发人员都知道是怎么回事好吗?不就是用来标记和分组代码的吗?难道还有别的装逼技能? 当然,其实问大部分人说这两个是什么作用,或者是除了这两个还知道什么的情况 ...
-
NFinal 视图—用户控件
自定义控件 定义控件 以Label控件为例: 1.首先在Common文件夹下添加Label.cs文件,其中代码如下: //a.control的实体类必须继承NFinal.UserControl类 pu ...
-
nginx与ios实现https双向认证
服务端配置 nginx关键配置例如以下: listen 443; server_name localhost; ssl on; ssl_certificate /usr/local/opt/nginx ...
-
题目1083:特殊乘法-九度oj
题目描述: 写个算法,对2个小于1000000000的输入,求结果. 特殊乘法举例:123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5 输入: 两个小于1000000000的 ...
-
linux常用命令(不断更新)
睡眠命令(第一步可省去): 1.查看你的系统支持什么模式:cat /sys/power/state(我的系统为:freeze mem disk) 2.切换到管理员模式下,执行命令:echo " ...
-
python中如何将生成等差数列和等比数列
在python库numpy 中提供了函数linspace和logspace函数用于生产等差数列和等比数列. 1.linspace函数生成等差数列 def linspace(start, sto ...
-
Salesforce 外部对象
外部对象(External Object) 在Salesforce中,管理员或开发者可以通过"外部对象"将其他系统中的数据虚拟地展现为Salesforce的对象.每个外部对象都要连 ...
-
EF5+MVC4系列(11)在主视图中用Html.RenderPartial调用分部视图(ViewDate传值);在主视图中按钮用ajax调用子action并在子action中使用return PartialView返回分布视图(return view ,return PartialView区别)
一:主视图中使用Html.RenderPartial来调用子视图(注意,这里是直接调用子视图,而没有去调用子Action ) 在没有使用母版页的主视图中(也就是设置了layout为null的视图中), ...
-
android studio 卡慢的问题(android studio 3.0)
http://www.jianshu.com/p/0228b7d017bb 想体验一下android studio 3.0的canary版,主要是学习Kotlin.创建项目后,下载相关文件一直不成功. ...