• 題目

內(nèi)存限制：256.0MB? Java時間限制：3.0s?

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設,魚臺企業(yè)網(wǎng)站建設,魚臺品牌網(wǎng)站建設,網(wǎng)站定制,魚臺網(wǎng)站建設報價,網(wǎng)絡營銷,網(wǎng)絡優(yōu)化,魚臺網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

問題描述

炫炫開了一家商店，賣的貨只有一個，XXX，XXX賣N元錢。有趣的是，世界上只有面值為3的冪的紙幣，即紙幣只有1元的、3元的、9元的。。。。，有一天，橋神來買XXX，可他沒辦法正好給出N元錢，而炫炫沒法找零，于是他只好用他的錢湊出了一個比N大，并且最小的價值，交給了炫炫。炫炫想知道，他這次最多可以得到多少張紙幣。

輸入格式

一個數(shù)，N

輸出格式

一個數(shù)，為答案

樣例輸入

4

樣例輸出

2

• 分析：

  • 這題和貪心算法中最常出現(xiàn)的零錢問題有點相似。

  • 題目有三個條件：1.是橋神的錢數(shù)不可以等于N，也就是說橋神的錢數(shù)只能>N。2.是要求炫炫收到的紙幣張數(shù)要大。3.紙幣的面值都是3的冪。

  • 分兩種情況，第一種是如果N是3的倍數(shù)，那么他支付的面值只能是大的不超過N的3的冪指數(shù)，即floor(log(3)N)+1。（因為如果面值不是這樣的話，可以他們是可以湊到N的，就不符合題意了）。第二種是N不是3的倍數(shù)，則可以用3來湊，只要有N/3+1張面值為3的紙幣即可（1不可能用，因為1是絕對可以湊到N的，用3的冪就達不到題目說的最多紙張要求了）。

• 思路：貪心算法

  • 按照上方的分析，顯示第一種情況N不是3的倍數(shù)，則N/3+1即可

  • 另一種情況，按照上面的思路是算出大的不超過N的3的冪指數(shù)，但是題目的數(shù)據(jù)規(guī)模要用long，Java的Math類提供的函數(shù)只能是double型，所以要用其他方法。所以這里用的是將N/3找出第一個不是3的倍數(shù)，然后用第一種情況算。

• 代碼：

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的冪指數(shù)為3時，要多少張3元紙🖊
        }
        System.out.println(sum);
    }
}

（有錯誤歡迎指正哈，如果有不小心侵權的聯(lián)系刪除哈😁）?

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞標題：藍橋杯---幸運的店家-創(chuàng)新互聯(lián)
分享鏈接：http://www.rwnh.cn/article22/cepojc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、全網(wǎng)營銷推廣、動態(tài)網(wǎng)站、網(wǎng)站設計、定制開發(fā)、營銷型網(wǎng)站建設

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)