贪心算法-----柠檬水找零

今日题目：leetcode860

题目链接：点击跳转题目

分析：

顾客只会给三种面值：5、10、20，先分类讨论

• 当收到5美元时：不用找零，面值5张数+1
• 当收到10美元时：找零5美元，面值5张数-1、面值10张数+1
• 当收到20美元时：找零15美元，两种情况
  • 一张10美元 、 一张5美元
  • 三张5美元

对于收到20美元时，该以什么为评判标准来选择用哪一种找零方式呢？

纵观三种情况，收到10、20美元时都会用到5美元，而10美元只有收到20美元时才可能使用；

贪心思路：为了能尽可能多的正确找零，所以当收到20美元时，尽量以10+5的方式找零，除非没有10没有再不得以用三张5美元，因为5美元的找零作用很大！

代码：

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five_nums = 0;int ten_nums = 0;for(auto & x : bills){if(x == 5) {five_nums++;continue;}if(x == 10) {ten_nums++;if(five_nums > 0) five_nums--;else return false;}if(x == 20){if(five_nums >0 && ten_nums > 0){five_nums--;ten_nums--;}else if(ten_nums ==0 && five_nums >= 3){five_nums -= 3;}else return false;}}return true;}
};