当前位置： 移动技术网 > IT编程>开发语言>C/C++ > JZOJ.1153【贪心算法】硬币交换

JZOJ.1153【贪心算法】硬币交换

2019年08月01日  | 移动技术网IT编程  | 我要评论

穿越时空之猎艳天下,白雪公主与猎人下载,衰弱的阿瑟隆

好难啊！！！

可聪明的我还是解出来了！（逃

题目描述

  小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. 如果不，则将现有金钱通过兑换减少。（1个金币，2次交换 金->银->金，减为原来的9/11）
  3. 重复1，2，直到刚好换到所需的钱。

码完代码，提交到oj，真是：

tle里说今年，听取wa~声一片！

介才系建切希露：

  1. 将银币换为所需金币和铜币。
  2. 判断已有银币和所需银币的大小。
  3. 若所需银币大于已有银币，则是impossible。
  4. 反之则模拟 暴力 次数。

代码在这儿（说得这么明白，都不想放了）

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网