HDU 1009 FatMouse‘ Trade （贪心算法）

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

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

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

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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;
}

相关阅读:
带有 Spring AOP 和自定义注解的 Java 观察者模式
Wincc报表教程(SQL数据库的建立，wincc在数据库中保存和查询数据，调用Excel模板把数据保存到指定的位置和打印功能)
【毕业设计源码】基于Python的校园生活助手（二手+活动+论坛+新闻）信息系统
Linux上防火墙操作
Vue（Vuex插件）
21.Node-RESTful API的用法
Nodejs安装及环境配置
【一起学数据结构与算法】还不会哈希表吗？一篇让你学会哈希表
stable diffusion安装踩坑之clip安装、git报错
【ARC116F】Deque Game 题解

原文地址：https://blog.csdn.net/liuliuhelingdao/article/details/128009025