【1009 HDU】FatMouse' Trade

痛定思痛。 2022-05-13 06:18 202阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1009][http_acm.hdu.edu.cn_showproblem.php_pid_1009]

题意：老鼠有M磅猫粮，它要去跟猫做交易，拿它的猫粮换鼠粮，现有n个房间，第i个房间都有J\[i\]磅的鼠粮，同时需要支付F\[i\]磅猫粮，但是老鼠可以不用把鼠粮全部换走，即它可以用x磅的猫粮换取x\*（J\[i\] / F\[i\]）的鼠粮，问M磅猫粮最多可以获取鼠粮的重量。

思路：贪心算法，求最优解。将J\[i\]/F\[i\]的值从大到小排列，总是先取最大的，就能保证能够得出的是最大值

My DaiMa：

#include <iostream>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    struct person
    {
    	double a,b,pi;
    }s[1003];
    bool cmp1(person p1, person p2)
    {
    	return p1.pi > p2.pi;
    }
    int main()
    {
    	int n, m;
    	while (cin >> m >> n)
    	{
    		if (m == -1 || n == -1)
    			break;
    		else
    		{
    			for (int i = 0; i < n; i++)
    			{
    				cin >> s[i].a >> s[i].b;
    				s[i].pi = s[i].a / s[i].b;
    			}
    			sort(s, s + n, cmp1);//根据兑换率对结构体进行排序
    			double ans = 0;
    			for (int i = 0; i < n; i++)
    			{
    				if (m >= s[i].b)
    				{
    					m -= s[i].b;
    					ans += s[i].a;//表示它的猫粮够换取这个房间里的所有鼠粮
    				}
    				else
    				{
    					ans += s[i].pi*m;//用它剩下的猫粮乘以兑换率
    					break;
    				}
    			}
    			printf("%.3lf\n", ans);
    		}
    	}
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1009]: http://acm.hdu.edu.cn/showproblem.php?pid=1009

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关【杭电1009】FatMouse' Trade

![这里写图片描述][20160722140132324] ![这里写图片描述][20160722140141652] 结合结构体，贪心，浮点数做分母可为零。贪心的标准

Bertha 。/ 2022年09月24日 01:22/ 0 赞/ 128 阅读

相关 FatMouse' Trade

FatMouse' Trade Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 FatMou

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 05:59/ 0 赞/ 141 阅读

相关 HDOJ 1009-FatMouse' Trade【贪心】

FatMouse' Trade Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

我会带着你远行/ 2022年07月16日 17:53/ 0 赞/ 155 阅读

相关 hdu 1009 FatMouse' Trade

FatMouse' Trade Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

灰太狼/ 2022年06月16日 12:54/ 0 赞/ 175 阅读

相关 HDU 1009 FatMouse' Trade (贪心)

//题意自己看，不会度娘，很裸的贪心，没啥好说的 include <stdio.h> include <string.h> include <

超、凢脫俗/ 2022年06月04日 05:10/ 0 赞/ 183 阅读

相关【1009 HDU】FatMouse' Trade

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1009][http_acm.hdu.edu.cn_showproblem.ph

痛定思痛。/ 2022年05月13日 06:18/ 0 赞/ 203 阅读

相关 FatMouse’ Trade

简介贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法

╰半橙微兮°/ 2022年04月24日 06:20/ 0 赞/ 169 阅读

相关 HDU 1009 FatMouse' Trade

原题目链接[HDU1009][] -------------------- 分类 HDU 贪心 -------------------- 题意贪心专题

末蓝、/ 2022年04月16日 04:59/ 0 赞/ 180 阅读

相关 HDU-1009——FatMouse' Trade

[ FatMouse' Trade][FatMouse_ Trade] Problem D

「爱情、让人受尽委屈。」/ 2022年04月11日 09:54/ 0 赞/ 176 阅读

相关 FatMouse' Trade

题目连接：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40692\problem/A][http_acm.hu

「爱情、让人受尽委屈。」/ 2021年06月24日 13:58/ 0 赞/ 214 阅读