文档章节

贪心之老鼠与猫的交易(详细分析)

o
 osc_ea6pnve7
发布于 07/07 17:12
字数 517
阅读 10
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

题目描述

有一只老鼠很喜欢奶酪,但是奶酪被分别放在N个房间里,而且这些房间都有一只猫咪看守,现在它准备和猫咪们做个交易。它有M磅的猫食,想用这M磅猫食换取奶酪。在猫咪看守的每一个房间里有奶酪J[i]磅,同时猫咪需要F[i]磅的食物,如果老鼠给猫咪F[i](a)%的猫食,那么它就可以得到J[i](a)%的奶酪。现在已知每只猫咪对猫食的需求量和每个房间的奶酪数,那老鼠怎样才能换得最多的奶酪呢?

输入格式
第一行输入两个正整数M和N(M和N不大于10000),后面跟N行(每个房间的奶酪数和猫食的需求量)。
输出格式
输出老鼠得到的最多的奶酪数,保留三位小数。


样例

样例1输入
5 3
7 2
4 3
5 2
样例1输出
13.333





样例2输入
20 3
25 18
24 15
15 10
样例2输出
31.500





算法分析

这一题很明显为贪心算法,但因为a不定,所以最为困难的就是a%。而这时候,易发现当a[i].j很小而a[i].f很大时,这是我们最想要的情况,所以简洁来说就是当a[i].f/a[i].j最大时,是我们最佳贪心策略

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100005;
struct cat{
	int f,j;
	double tot;//f/j的值
}a[M];
bool cmp(cat x,cat y){//将tot排序处理
	if(x.tot<y.tot)
	return false;
	return true;
}
int main(){
	int m,n;
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a[i].f,&a[i].j);
		a[i].tot=a[i].f*1.0/a[i].j;
	}
	sort(a+1,a+1+n,cmp);
	double sum=0;
	for(int i=1;i<=n;i++){
		if(m>=a[i].j){
			m-=a[i].j,sum+=a[i].f;
		}
		else{
			double id=m*1.0/a[i].j;
			sum+=a[i].f*1.0*id;
			break;//最后处理剩下的m
		}
	}
	printf("%.3lf",sum);
} 
o
粉丝 0
博文 82
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Flappy Bird(安卓版)逆向分析(一)

更改每过一关的增长分数 反编译的步骤就不介绍了,我们直接来看反编译得到的文件夹 方法1:在smali目录下,我们看到org/andengine/,可以知晓游戏是由andengine引擎开发的。打开/res/raw/at...

enimey
2014/03/04
5.9K
18
实时分析系统--istatd

istatd是IMVU公司工程师开发的一款优秀的实时分析系统,能够有效地收集,存储和搜索各种分析指标,类似cacti,Graphite,Zabbix等系统。实际上,istatd修改了Graphite的存储后端,重新实现了...

匿名
2013/02/07
2.8K
1
日志分析平台 - Kibana

Kibana 是一个为 Logstash 和 ElasticSearch 提供的日志分析的 Web 接口。可使用它对日志进行高效的搜索、可视化、分析等各种操作。 环境要求: ruby >= 1.8.7 (probably?) bundler logstash...

匿名
2013/02/13
11.5W
1
Swing界面分析和调试工具--Swing Inspector

Swing Inspector是一个Java Swing/AWT用户界面分析和调试工具,功能与firebug类似,具有强大的Swing/AWT用户界面分析和调试相关功能。 适用于从java swing初级到高级的所有开发人员,能够快速...

匿名
2013/03/06
3.3K
0
购物车开源模块--FishCart

FishCartSQL 是一个功能齐全的购物车开源模块,可以在里面增加一些自己喜欢的页面。里面有许多高级特性,如:用户记录、即时交易、多语言支持、信用卡处理和单服务吕部署多个在线商店,里面用...

匿名
2013/03/27
1.7K
0

没有更多内容

加载失败,请刷新页面

加载更多

MySql大表分页(附独门秘技)

问题背景 MySql(InnoDB)中的订单表需要按时间顺序分页查询,且主键不是时间维度递增,订单表在百万以上规模,此时如何高效地实现该需求? 注:本文并非主要讲解如何建立索引,以下的分析均建...

osc_8kei32r9
31分钟前
0
0
css中使用变量

2017年3月,微软宣布 Edge 浏览器将支持 CSS 变量。 这个重要的 CSS 新功能,所有主要浏览器已经都支持了。 声明css变量的时候,变量名前面要加两根连词线(--)。 变量名大小写敏感,--hea...

osc_mpdswsal
31分钟前
0
0
WAS 忘记密码

一、重置密码 1.首先关闭was,ps –ef|grep java 查看java进程号,然后kill -9 XXXX杀掉进程即可。或者使用命令./stopServer.sh server1 2.取消控制台安全验证 方法一:/opt/IBM/WebSphere/...

osc_1i3ltp99
32分钟前
0
0
npm install的--save选项是什么? - What is the --save option for npm install?

问题: I saw some tutorial where the command was: 我看到了一些命令所在的教程: npm install --save What does the --save option mean? --save选项是什么意思? Not able to find the......

fyin1314
33分钟前
5
0
C#使用读写锁三行代码简单解决多线程并发写入文件时线程同步的问题

在开发程序的过程中,难免少不了写入错误日志这个关键功能。实现这个功能,可以选择使用第三方日志插件,也可以选择使用数据库,还可以自己写个简单的方法把错误信息记录到日志文件。 选择最...

osc_7cws6vmd
34分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部