贪心算法——找纸币问题
问题主题:找钱 |
问题描述: 假设有1元、2元、5元、10元、20元、50元、100的纸币分别为c0, c1, c2, c3, c4, c5, c6,张。现在要用这些钱来支付K元,至少要用多少张纸币?如果能找,则输出纸币的张数,不能找则输出No 限制条件: 0<=c0, c1,c2,c3,c4,c5,c6<=109 0<=K<=109 |
样例: 输入 C0=3, c1=0, c2=2, c3=1, c4=0, c5=3, c6=5 输出 6 |
本题使用贪心算法,只需要考虑“尽可能多地使用面值大的纸币”,然后根据面值的大小从大到小排序依次选择。
C++
#include "iostream" |