HDU 1009 FatMouse' Trade

末蓝、 2022-04-16 04:59 148阅读 0赞

## 原题目链接[HDU1009][] ##

--------------------

## 分类 ##

HDU 贪心

--------------------

## 题意 ##

**贪心专题**  
一共有n个房子，每个房子里有老鼠喜欢吃的javabeans,但是每个房间里的javabeans的价格不一样。老鼠用m元，问m元最多可以卖多少javabeans，其中每个房间里的javabeans可以被分割。

--------------------

## 样例输入输出 ##

Sample Input

5 3
    7 2
    4 3
    5 2
    20 3
    25 18
    24 15
    15 10
    -1 -1

Sample Output

13.333
    31.500

--------------------

## 想法 ##

先求单价，然后排个序（sort重载cmp）

--------------------

## 代码 ##

62ms

#include<bits/stdc++.h>
    #define maxn 1111
    using namespace std;
    struct good{ 
    	double v,w;
    }goods[maxn];
    bool cmp(good a,good b){ 
    	return b.v/b.w < a.v/a.w;
    }
    int main()
    { 
    	int	n;
    	double m,ans;
    	while(scanf("%lf%d",&m,&n)!=EOF){ 
    		if(m==-1&&n==-1) break;
    		for(int i=0;i<n;i++){ 
    			scanf("%lf%lf",&goods[i].v,&goods[i].w);
    		}
    		ans = 0;
    		sort(goods,goods+n,cmp);
    		for(int i=0;i<n;i++){ 
    			
    			if(m>=goods[i].w){ 
    				ans += goods[i].v;
    				m   -= goods[i].w; 
    			}else{ 
    				ans += (double)(m *(double)(goods[i].v / goods[i].w));
    				break;
    			}
    		}
    		printf("%.3lf\n",ans);
    	} 
        return 0;
    }

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

发表评论取消回复

表情：

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

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

相关阅读

相关【杭电1009】FatMouse' Trade

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

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

相关杭电1009-FatMouse' Trade（贪心）

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

青旅半醒/ 2022年08月08日 14:53/ 0 赞/ 18 阅读

相关 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 赞/ 117 阅读

相关 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 赞/ 135 阅读

相关 HDU 1009 FatMouse' Trade (贪心)

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

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

相关 HDU-FatMouse' Trade （贪心）

FatMouse' Trade Problem Description FatMouse prepared M pounds of cat food,

心已赠人/ 2022年05月26日 04:22/ 0 赞/ 132 阅读

相关【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 赞/ 172 阅读

相关 FatMouse’ Trade

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

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

相关 HDU 1009 FatMouse' Trade

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

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

相关 HDU-1009——FatMouse' Trade

[ FatMouse' Trade][FatMouse_ Trade] Problem D

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