【贪心算法】之买柠檬水找零

有如下三种情况：

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再考虑消耗三个5

账单是20的情况，为什么要优先消耗一个10和一个5呢？

? 美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！
? 所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

package 算法.贪心算法.简单;
//有如下三种情况：
//情况一：账单是5，直接收下。
//情况二：账单是10，消耗一个5，增加一个10
//情况三：账单是20，优先消耗一个10和一个5，如果不够，再考虑消耗三个5
//账单是20的情况，为什么要优先消耗一个10和一个5呢？
//因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！
//所以局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
public class leetcode_860 {
    public static void main(String[] args) {
        int[] bills={5,5,10,10,20};
        System.out.println(lemonadeChange(bills));
    }

    public static boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            //情况1
            if (bill == 5) {
                five++;
            }
            //情况2
            if (bill == 10) {
                if (five <= 0) {
                    return false;//不满足10的找零就返回false
                }
                five--;
                ten++;
            }
            //情况3
            if (bill == 20) {
                // 优先消耗一个10和一个5
                if (ten >0 && five>0){
                    five--;
                    ten--;
                    //如果不够，再考虑消耗三个5
                }else if (five>=3){
                    five-=3;
                }else {
                    return false;//不满足20的找零就返回false
                }
            }
        }
        return true;
    }
}