devbox
酷酷是懒虫
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯---幸运的店家_蓝桥杯幸运的店家

作者：酷酷是懒虫 | 2024-08-04 22:54:05

赞

踩

蓝桥杯幸运的店家

  •  题目

内存限制：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的倍数，然后用第一种情况算。

  • 代码：

  1. package BlueBridge;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class LuckyStore {
  6.     public static void main(String[] args) {
  7.         Scanner in = new Scanner(System.in);
  8.         long n = in.nextLong();
  9.         long sum = 0;
  10.         if (n%3!=0)  //第一种情况
  11.             sum = (n/3)+1;
  12.         else {  //第二种情况
  13.             while (n % 3 == 0)
  14.                 n = n / 3;
  15.             sum = (n/3)+1;  //等价于最大的且不大于N的3的幂指数为3时，要多少张3元纸
    声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/929813
    推荐阅读
    相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。