NYOJ-914 Youth的最大化(贪心)

时间:2022-08-28 09:27:34

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的最大化(贪心)的更多相关文章

  1. NYOJ 914 Yougth的最大化

    Yougth的最大化 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描写叙述 Yougth如今有n个物品的重量和价值各自是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价 ...

  2. NYOJ 914 Yougth的最大化【二分&sol;最大化平均值模板&sol;01分数规划】

    914-Yougth的最大化 内存限制:64MB 时间限制:1000ms 特判: No 通过数:3 提交数:4 难度:4 题目描述: Yougth现在有n个物品的重量和价值分别是Wi和Vi,你能帮他从 ...

  3. NYOJ 1107 最高的奖励&lpar;贪心&plus;优先队列&rpar;

    最高的奖励 时间限制:1000 ms  |  内存限制:65535 KB 难度:3   描述 请问:挖掘机技术哪家强?AC了告诉你! 给你N(N<=3*10^4)个任务,每个任务有一个截止完成时 ...

  4. nyoj 47——过河问题——————【贪心】

    过河问题 时间限制:1000 ms  |  内存限制:65535 KB 难度:5   描述 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的 ...

  5. NYIST 914 Yougth的最大化

    Yougth的最大化时间限制:1000 ms | 内存限制:65535 KB难度:4 描述 Yougth现在有n个物品的重量和价值分别是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价值最大吗? ...

  6. nyoj 208 &plus; poj 1456 Supermarket &lpar;贪心&rpar;

    Supermarket 时间限制:1000 ms  |  内存限制:65535 KB 难度:4   描述 A supermarket has a set Prod of products on sal ...

  7. nyoj 14-会场安排问题 &lpar;贪心&rpar;

    14-会场安排问题 内存限制:64MB 时间限制:3000ms Special Judge: No accepted:9 submit:15 题目描述: 学校的小礼堂每天都会有许多活动,有时间这些活动 ...

  8. nyoj 448 寻找最大数(贪心专题)

    寻找最大数 时间限制:1000 ms  |  内存限制:65535 KB 难度:2   描述 请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大, 比如当n=920813467185 ...

  9. nyoj 91 阶乘之和(贪心)

    阶乘之和 时间限制:3000 ms  |  内存限制:65535 KB 难度:3   描述 给你一个非负数整数n,判断n是不是一些数(这些数不允许重复使用,且为正数)的阶乘之和,如9=1!+2!+3! ...

随机推荐

  1. easyui DataGrid 工具类之 TableUtil class

    import java.lang.reflect.InvocationTargetException;import java.util.ArrayList;import java.util.HashM ...

  2. 聊聊 &num;pragma 和 &sol;&sol; MARK&colon;

    我去,就这两个东西还要讲?是OC或Swift开发人员都知道是怎么回事好吗?不就是用来标记和分组代码的吗?难道还有别的装逼技能? 当然,其实问大部分人说这两个是什么作用,或者是除了这两个还知道什么的情况 ...

  3. NFinal 视图—用户控件

    自定义控件 定义控件 以Label控件为例: 1.首先在Common文件夹下添加Label.cs文件,其中代码如下: //a.control的实体类必须继承NFinal.UserControl类 pu ...

  4. nginx与ios实现https双向认证

    服务端配置 nginx关键配置例如以下: listen 443; server_name localhost; ssl on; ssl_certificate /usr/local/opt/nginx ...

  5. 题目1083:特殊乘法-九度oj

    题目描述: 写个算法,对2个小于1000000000的输入,求结果. 特殊乘法举例:123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5 输入: 两个小于1000000000的 ...

  6. linux常用命令(不断更新)

    睡眠命令(第一步可省去): 1.查看你的系统支持什么模式:cat /sys/power/state(我的系统为:freeze mem disk) 2.切换到管理员模式下,执行命令:echo &quot ...

  7. python中如何将生成等差数列和等比数列

    在python库numpy 中提供了函数linspace和logspace函数用于生产等差数列和等比数列.     1.linspace函数生成等差数列 def linspace(start, sto ...

  8. Salesforce 外部对象

    外部对象(External Object) 在Salesforce中,管理员或开发者可以通过"外部对象"将其他系统中的数据虚拟地展现为Salesforce的对象.每个外部对象都要连 ...

  9. EF5&plus;MVC4系列&lpar;11&rpar;在主视图中用Html&period;RenderPartial调用分部视图&lpar;ViewDate传值&rpar;&semi;在主视图中按钮用ajax调用子action并在子action中使用return PartialView返回分布视图&lpar;return view &comma;return PartialView区别&rpar;

    一:主视图中使用Html.RenderPartial来调用子视图(注意,这里是直接调用子视图,而没有去调用子Action ) 在没有使用母版页的主视图中(也就是设置了layout为null的视图中), ...

  10. android studio 卡慢的问题&lpar;android studio 3&period;0&rpar;

    http://www.jianshu.com/p/0228b7d017bb 想体验一下android studio 3.0的canary版,主要是学习Kotlin.创建项目后,下载相关文件一直不成功. ...