Poj百练 4110:圣诞老人的礼物-Santa Clau’s Gifts (分类:贪心)
发布日期:2021-06-29 15:52:18
浏览次数:2
分类:技术文章
本文共 847 字,大约阅读时间需要 2 分钟。
#include#include #include using namespace std;const int maxn = 100+5;int n, w;struct Box{ int v, w; double den;};bool operator < (const Box &a, const Box &b) //重载比较{ return a.den>b.den;}int main(){ scanf("%d%d",&n,&w); Box boxes[maxn]; for(int i = 1; i <= n; i++){ scanf("%d%d",&boxes[i].v, &boxes[i].w); //直接计算出每个礼物的性价比 boxes[i].den = 1.0*boxes[i].v/boxes[i].w; } //按升序进行排序 sort(boxes+1, boxes+n+1); //按性价比从高到低依次向下取 double totw = 0, totv = 0; for(int i = 1; i <= n; i++){ if(w - totw >= boxes[i].w){ //可以放下 totw += boxes[i].w; totv += boxes[i].v; } else{ //放不下了 totv += boxes[i].den*(w-totw); totw += w; break; } } printf("%.1lf",totv); return 0;}
转载地址:https://suprit.blog.csdn.net/article/details/81415969 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月04日 15时28分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
CSS3&JavaScript 图片分隔切换
2019-04-29
CSS3&JavaScript 瀑布流
2019-04-29
tomcat配置JVM
2019-04-29
Oracle获取连接超级慢的问题
2019-04-29
关于HashMap初始化容量,设置多少合适。
2019-04-29
MYSQL 自定义函数
2019-04-29
早鸟票倒计时3天 | 2019携程技术峰会,11月9日上海(含福利)
2019-04-29
干货 | 微信小程序一键转百度小程序,携程火车票团队是这样做的
2019-04-29
沙龙回顾 | 移动互联网下的测试工程效率提升,含PPT和视频
2019-04-29
程里人 | 携程程序猿/媛的1024
2019-04-29
常见的字符集编码
2019-04-29
前端(一):字符与语义标签
2019-04-29
前端(二):CSS语法与选择器
2019-04-29
前端(三):样式继承与其他概念
2019-04-29
前端(四):样式继承与其他概念
2019-04-29
前端小案例:田径场
2019-04-29
前端(五):浮动
2019-04-29
前端(六):高度塌陷与BFC
2019-04-29
C++ 多线程
2019-04-29
C++ inline 内联函数
2019-04-29