腾讯正常批笔试一：硬币题

问题描述

小Q去商场购物，经常会遇到找零的问题。
小Q现在手上有n种不同面值的硬币，每种面值的硬币都有无限多个。
为了方便购物，小Q希望带尽量少的硬币，并且要能组合出1到m之间（包含1和m）的面值。

输入描述

第一行包含两个整数m，n
接下来的n行表示n种硬币的面值

输出格式

最少需要携带的硬币数量，如果无解则输出-1

样例输入

20 4
1
2
5
10

输出

5

数据范围

1<=m<=10^9，1<=n<=100

---

一开始真的不会做，后来看了大佬们的思路才知道如何解，记录一下这个题。

分析如下

看似背包，其实是贪心：从1逐渐满足到m的策略。
假设现在硬币 res = [1,2] 表示当前使用了一个1面值的硬币，一个2面值的硬币，在这种情况下，你能表示区间 sum= 3 以内的所有数据（线性组合）。此时考虑再加一枚什么面值的硬币最优，使他之后的区间满足。之后的区间为：[当前能满足区间的最大值, 候选硬币值）, 也就是[3, 5), 当前的硬币组合是不能满足这个区间要求的（4这个元素满足不了）。因此我们应该贪心的加上一个当前面值最大的硬币，也就是面值为2的硬币，也就是说 res = [1,2,2] , 此时的线形组合能满足的最大区间为 sum = 3+2 = 5 , 也就是说可以满足了,以此类推往下继续走.

代码:

#coding=utf-8
import sys
if __name__ == "__main__":
    lines = sys.stdin.readlines()
    m, n = list(map(int, lines[0].strip().split()))
    coins = []
    for line in lines[1:]:
        coins.append(int(line.strip()))

    su = coins[0]
    res = [coins[0]]
    i = 1
    while(i<n):
        if su >= (coins[i] - 1):
             i += 1
        else:
            res.append(coins[i-1])
            su += res[-1]
    while(su<m):
        res.append(coins[-1])
        su += res[-1]
    print len(res)

总结

其实是一道区间贪心的题目，还是经受的毒打太少了。 WechatIMG94.jpeg

(循环处的贪心思想代码还可以再精简，直接统计个数，不需要开辟res数组空间，只是为了调试）