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

//柠檬水找零
/*
* 在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排队购买你的产品，一次购买一杯
* 每位顾客只买一杯柠檬水，然后向你支付5美元、10美元或者20美元。必须给每个顾客正确找零
* 注意，一开始你手上没有任何零钱
* 如果你能给每位顾客正确找零，返回true，否则返回false
* */
public class P20 {
    public static void main(String[] args) {
        System.out.println(change(new int[]{5,5,20}));
        System.out.println(change(new int[]{5,5,10}));
    }

    //贪心算法
    //假设顾客付5没有，不需要找零
    //假设顾客付10美元，需要找5美元
    //假设顾客付20美元，需要优先找10+5，没有的时候再找5+5+5，因为5是万能的，可应付所有顾客
    //20美元对找零没有意义，只需要记录有几张5块，几张10块
    public static boolean change(int[] bills){

        int five = 0;
        int ten = 0;

        for(int i=0; i<bills.length; i++){
            if(bills[i] == 5){
                five++;
            } else if(bills[i] == 10){
                if(five == 0){      //找零需要一张
                    return false;
                }else{
                    five--;
                    ten++;
                }
            }else{
                if(five > 0 && ten > 0){
                    five--;
                    ten--;
                }else if(five >= 3){
                    five -= 3;
                }else{
                    return false;
                }
            }
        }

        return true;
    }
}