贪心法之柠檬水找零_贪心法柠檬水找零

题目: 

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。 你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。 如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1： 输入：[5,5,5,10,20] 输出：true

思路:

1. 设置两个变量 five_count 和 ten_count 分别表示手里拥有的 5 美元和 10 美元的数量，初始值都为 0。

2. 遍历每个顾客支付的金额，如果是 5 美元，则不需要找零；如果是 10 美元，则需要找回 5 美元；如果是 20 美元，则需要找回 15 美元。

3. 对于 10 美元的找零，我们需要首先判断手里是否有足够的 5 美元来找零。如果有，则将 five_count 减 1，将 ten_count 加 1；如果没有，则无法找零，返回 false。

4. 对于 20 美元的找零，我们需要优先使用一张 10 美元和一张 5 美元来找零，因为这样可以让手里的 5 美元硬币更多，以备后续使用。如果手里没有足够的 10 美元和 5 美元，则可以使用三张 5 美元来找零。如果无法找零，返回 false。

5. 如果所有顾客的交易都能正确找零，最终返回 true。

代码:

#include <iostream>
using namespace std;
#include <vector>
 
// 找零函数，接受一个整数向量表示账单，返回是否能找零的布尔值
bool lemonadeChange(vector<int>& bills) {
    int five_count = 0;  // 5 美元钞票数量
    int ten_count = 0;   // 10 美元钞票数量
 
    // 遍历账单
    for (int bill : bills) {
        if (bill == 5) {  // 如果是 5 美元
            five_count++;  // 5 美元数量加一
        }
        else if (bill == 10) {  // 如果是 10 美元
            if (five_count >= 1) {  // 如果有 5 美元可以找零
                five_count--;       // 找零 5 美元
                ten_count++;        // 得到 10 美元
            }
            else {  // 无法找零
                return false;
            }
        }
        else if (bill == 20) {  // 如果是 20 美元
            if (ten_count >= 1 && five_count >= 1) {  // 如果有 10 美元和 5 美元可以找零
                ten_count--;      // 找零 10 美元
                five_count--;     // 找零 5 美元
            }
            else if (five_count >= 3) {  // 如果没有 10 美元，但有 3 张 5 美元可以找零
                five_count -= 3;  // 找零 3 张 5 美元
            }
            else {  // 无法找零
                return false;
            }
        }
    }
 
    return true;  // 能够成功找零
}
 
int main() {
    vector<int> bills = { 5, 5, 5, 10, 20 };
    bool result = lemonadeChange(bills);
    cout << boolalpha << result << endl;  // 输出：true
    return 0;
}