JZOJ.1153【贪心算法】硬币交换
2019-08-16 07:56:06来源:博客园 阅读 ()
JZOJ.1153【贪心算法】硬币交换
好难啊!!!
可聪明的我还是解出来了!(逃
题目描述
小z最近迷上了一款游戏――To Be A Farmer,他在游戏中控制的人物是一个叫FZ的Farmer。FZ身上有G1个金币、S1个银币和B1个铜币,而他至少需要G2个金币、S2个银币和B2个铜币。为了完成这个目标,小z只好控制FZ来到了游戏中的银行。银行有如下规定:
(1)你可以用1个金币交换9个银币;
(2)你可以用11个银币交换1个金币;
(3)你可以用1个银币交换9个铜币;
(4)你可以用11个铜币交换1个银币;
小z看到这些规定,顿时头大了,只好求助于你。聪明的你来帮助他解决这样一个问题:最少需要交换多少次硬币才能至少拥有G2个金币、S2个银币和B2个银币呢?
输入
第1行包含三个整数:G1、S1和B1。
第2行包含三个整数:G2、S2和B2。
0 ≤ G1、S1、B1、G2、S2、B2 ≤ 10000000。
输出
如果可以完成任务的话,输出一个整数表示最少交换次数;否则输出整数-1。
样例输入
10 0 0
0 0 81
样例输出
10
初步思路:
- 判断可不可以刚好用完。
- 如果不,则将现有金钱通过兑换减少。(1个金币,2次交换 金->银->金,减为原来的9/11)
- 重复1,2,直到刚好换到所需的钱。
码完代码,提交到OJ,真是:
TLE里说今年,听取WA~声一片!
介才系建切希露:
- 将银币换为所需金币和铜币。
- 判断已有银币和所需银币的大小。
- 若所需银币大于已有银币,则是Impossible。
- 反之则模拟
暴力次数。
代码在这儿(说得这么明白,都不想放了)
#include<bits/stdc++.h>
using namespace std;
int a1,b1,c1,a2,b2,c2,ans;
int main()
{
cin>>a1>>b1>>c1>>a2>>b2>>c2;
if(a1 < a2)
{
ans+=a2-a1;
b1-=(a2-a1)*11;
a1=a2;
}
if(c1 < c2)
{
ans+=(c2-c1+8)/9;
b1-=(c2-c1+8)/9;
c2+=(c2-c1+8)/9*9;
}
if(b1 < b2 && a1 > a2)
{
if(b1+(a1-a2)*9 < b2)
{
ans+=(a1-a2);
b1+=(a1-a2)*9;
a1=a2;
}
else
{
ans+=(b2-b1+8)/9;
a1-=(b2-b1+8)/9;
b1+=(b2-b1+8)/9*9;
}
}
if(b1 < b2)
{
if(b1+(c1-c2)/11 >= b2)
{
ans+=(c1-c2)/11;
b1+=(c1-c2)/11;
c1-=(c1-c2)/11*11;
}
}
b1 >= b2 ? cout<<ans<<endl : cout<<-1<<endl;
return 0;
}
原文链接:https://www.cnblogs.com/Code-Garden/p/11283599.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:CentOS7安装高版本gcc
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash