筆試算法模拟題精解之“Bob的花束”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“66題.Bob的花束”的解法探究。先來看一下題目内容：

題目詳情：

等級：中等

知識點：貪心

檢視題目：66.Bob的花束

Bob和Alice是青梅竹馬。今天，Bob終于要鼓起勇氣向Alice表白了！說到表白，自然是少不了買花了。Bob來到了花店，花店一共提供了9種花，每一種花都有對應的價錢。但是Bob的零花錢有限，不能把所有的花都買下來送給Alice。

為了友善挑選，Bob給這9種花分别标号1-9，Bob希望買到的花按照編号可以排出盡可能大數字，請問Bob能夠排出的最大的數字是多少？

輸入一個正整數value，代表Bob擁有的零花錢。(0<=value<=10^6)

和有9個數字的數組a，ai代表第i種花的價格。(1<=ai<=10^5,1<=i<=9)

輸出一個數字，表示Bob可以排出的最大數字。如果Bob不能排出任何一個數字，則輸出-1。

示例1

輸入：

2

[9,11,1,12,5,8,9,10,6]

輸出：

33

注意:

花店的每一種花都可以視為無限多。

解題方法：模拟選花過程

本題充分了解題意後，直接模拟這個“選取最大值”的過程就可以得到結果了。

首先，選取最大值，意味着首先這個結果的“位數”要足夠多，比如假設所有的花價格都是1元錢，則11111111是花9塊錢能買到的最大值，而不是333或者9這樣的方案。這樣相當于根據輸入，輸出的位數可以用很小的時間代價來确定：“用可用錢數，除以最便宜的花的價格，并向下取整”。假設這裡的位數為m。

其次，在位數确定的情況下，高位數字越大，結果也就越大，比如同樣是8元錢，隻能購買價格為5的5号花，和價格為3的3号花時，購買35就是最差的方案，而53才是正确答案。而且因為每個花的數量是無限的，是以可以模拟這個 “從高位開始，逐個選取能買得起的最大的數字；同時每選完一位後，要確定剩下的錢，依舊可以買到m位數字的組合方案。”

提示： 根據上面邏輯寫出的答案，在充分了解優化後，至少可以達到2遍掃描數組得到結果。

時間複雜度：O(9n)

看完是不是有了新思路了呢，快來試一下吧：

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！

上一篇： 筆試算法模拟題精解之“完美排列” 下一篇： 筆試算法模拟題精解之“ 最優分組”的“周遊”解法