当前位置:首页 » 《随便一记》 » 正文

HDU 1009 FatMouse‘ Trade (贪心算法)

14 人参与  2022年11月28日 16:25  分类 : 《随便一记》  评论

点击全文阅读


题意:就是老鼠要用猫粮换粮食,第i个房间一些东西,要用东西去换,可以不全换。问给定的猫粮最多能换多少粮食。

析:贪心算法。我们先算出来每个房间物品的平均价格是多少,肯定越低越好,并且如果能全换就全换,如果不能,

肯定是最后一次了,就把剩下全部换了,看看能换多少。求和。

代码如下:

#include <iostream>#include <cstdio>#include <algorithm>#include <queue>#include <vector>#include <cstring>#include <map>#include <cctype>using namespace std;struct node{    double ave;   int x, y;    node() { }    node(int xx, int yy) : x(xx), y(yy), ave((double)xx/(double)yy) { }    bool operator < (const node &p) const {        return ave > p.ave;    }};node a[1005];int main(){    int n, m;    while(~scanf("%d %d", &n, &m) && (m+n != -2)){        int x, y;        for(int i = 0; i < m; ++i){            scanf("%d %d", &x, &y);            a[i] = node(x, y);        }        sort(a, a+m);        double ans = 0.0;        for(int i = 0; i < m; ++i){            if(n >= a[i].y){ ans += a[i].x;  n -= a[i].y;  }            else if(!n)  break;            else{                ans += a[i].ave * n;                n = 0;            }        }        printf("%.3lf\n", ans);    }    return 0;}

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/49199.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 填错志愿后,我成了活神仙章节目录_顾言姜澈林晓晓优质全文_小说后续在线阅读_无删减免费完结_
  • 沈亦初秦景泽后续(以后,她都不要再喜欢他了)(沈亦初秦景泽)整本畅享在线+无广告结局
  • 独家猎户夫君你轻点宠小说(云柔苏安)(猎户夫君你轻点宠)电子书畅享阅读
  • 全网首发容止洛云曦小说叫什么(他死后女帝火葬场了)(容止洛云曦)全书阅读纯净阅读
  • 周砚川战景熙小说章节目录+序章(离婚后,保镖前夫他成了财阀大佬)全书畅享在线
  • 碎骨惨死后,我与宿敌联手弑夫证道特别篇章节目录+章节前文(齐南韵柳苑云)TXT清爽版在线
  • 重生八零年代点天灯后,崇洋***的养妹疯了章节目录_肖颖芝江天肖星苒书荒_小说后续在线阅读_无删减免费完结_
  • 最新章节(姜小九徐琛)霸婚总裁小蛮妻:结局+番外精品选集附加章节列表
  • 死后十年,妈妈收到我的死亡通知高口碑_妹妹爸爸妈妈大丫隐藏剧情_小说后续在线阅读_无删减免费完结_
  • 邻居连续偷菜93天小说(林婉清顾星河)章节目录+起点章节(邻居连续偷菜93天)全篇清爽版在线
  • 何时慢顾砚之后续(你惹她干嘛?她带四十米大刀来了)(何时慢顾砚之)整本畅享在线+无广告结局
  • 结婚纪念日当天,老公说他出差了必读文_陆言林姗老公内容精选_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1