雲計算

Solution 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)

看完是不是有了新思路了呢,快来试一下吧:查看题目:66.Bob的花束

周赛、月赛火热进行中,更有限时答题活动,每天都有好礼相送~欢迎钉钉扫码入群交流~

在线编程用户交流群二维码.png

Leave a Reply

Your email address will not be published. Required fields are marked *