蓝桥杯---幸运的店家-创新互联

• 题目

内存限制：256.0MB  Java时间限制：3.0s 

成都创新互联公司是一家集网站建设,鱼台企业网站建设,鱼台品牌网站建设,网站定制,鱼台网站建设报价,网络营销,网络优化,鱼台网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

问题描述

炫炫开了一家商店，卖的货只有一个，XXX，XXX卖N元钱。有趣的是，世界上只有面值为3的幂的纸币，即纸币只有1元的、3元的、9元的。。。。，有一天，桥神来买XXX，可他没办法正好给出N元钱，而炫炫没法找零，于是他只好用他的钱凑出了一个比N大，并且最小的价值，交给了炫炫。炫炫想知道，他这次最多可以得到多少张纸币。

输入格式

一个数，N

输出格式

一个数，为答案

样例输入

4

样例输出

2

• 分析：

  • 这题和贪心算法中最常出现的零钱问题有点相似。

  • 题目有三个条件：1.是桥神的钱数不可以等于N，也就是说桥神的钱数只能>N。2.是要求炫炫收到的纸币张数要大。3.纸币的面值都是3的幂。

  • 分两种情况，第一种是如果N是3的倍数，那么他支付的面值只能是大的不超过N的3的幂指数，即floor(log(3)N)+1。（因为如果面值不是这样的话，可以他们是可以凑到N的，就不符合题意了）。第二种是N不是3的倍数，则可以用3来凑，只要有N/3+1张面值为3的纸币即可（1不可能用，因为1是绝对可以凑到N的，用3的幂就达不到题目说的最多纸张要求了）。

• 思路：贪心算法

  • 按照上方的分析，显示第一种情况N不是3的倍数，则N/3+1即可

  • 另一种情况，按照上面的思路是算出大的不超过N的3的幂指数，但是题目的数据规模要用long，Java的Math类提供的函数只能是double型，所以要用其他方法。所以这里用的是将N/3找出第一个不是3的倍数，然后用第一种情况算。

• 代码：

package BlueBridge;

import java.util.Scanner;

public class LuckyStore {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long sum = 0;
        if (n%3!=0)  //第一种情况
            sum = (n/3)+1;
        else {  //第二种情况
            while (n % 3 == 0)
                n = n / 3;
            sum = (n/3)+1;  //等价于大的且不大于N的3的幂指数为3时，要多少张3元纸🖊
        }
        System.out.println(sum);
    }
}

（有错误欢迎指正哈，如果有不小心侵权的联系删除哈😁） 

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：蓝桥杯---幸运的店家-创新互联
链接URL：http://bzwzjz.com/article/cepojc.html