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

HDU 1009 FatMouse‘ Trade (贪心算法)

12 人参与  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://zhangshiyu.com/post/49199.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

  • 家宴过后,我捉奸了庶妹和我老公无广告_庶妹老公侍卫TOP10_小说后续在线阅读_无删减免费完结_
  • 寝室六个人,她们背着我建五人群必读文_太天真申请书冷笑最新阅读_小说后续在线阅读_无删减免费完结_
  • 开局获得狐仙传承结局+番外_江帆赵雪隐藏剧情_小说后续在线阅读_无删减免费完结_
  • 刀锈春根生,白骨犹温完结全文_卫舟棠棠知意一口气完结_小说后续在线阅读_无删减免费完结_
  • 夫君立筷子定我灾星罪名,我改嫁冷宫皇子后他追悔莫及好评_赵荀孟如安青瑶精心编著_小说后续在线阅读_无删减免费完结_
  • 邻居低素质,而我没素质独家番外_老太太赖皮欣欣超长版_小说后续在线阅读_无删减免费完结_
  • 重生后我转嫁首富瘸腿独子,总裁前夫却疯了一口气看完_妹妹傅云琛沈明辉独家番外_小说后续在线阅读_无删减免费完结_
  • 我拒绝给系花捐款后,全系同学悔疯了在线阅读_小说后续在线阅读_无删减免费完结_
  • 我让位给女友的透视眼竹马,他却说如果能重生再也不来了。虐心反转_玉石林若女友推荐_小说后续在线阅读_无删减免费完结_
  • 相国独子的丫鬟砸坏我的玉佩后,我当场拒婚阅读_玉佩陈郡谢氏全新_小说后续在线阅读_无删减免费完结_
  • 手术时,我看着病人惨死最新试读_淼淼陆知衍姜颜全本完结_小说后续在线阅读_无删减免费完结_
  • 男友霸道给我开黑卡,转头却骂我是捞女最新章节_肖年顾客黑卡热文_小说后续在线阅读_无删减免费完结_

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

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