Title Link:/problems/lemonade-change/description/
Title Narrative:
At a lemonade stand, each glass of lemonade sells for 5 dollars. Customers line up to buy your product, one cup at a time (in the order the bills are paid).
Each customer buys a glass of lemonade and pays you $5, $10, or $20. You must give each customer the correct change, which means that the net transaction is that each customer pays you $5.
Note that at first you don't have any change on hand.
You are given an array of integers bills, where bills[i] is the bill paid by the ith customer. Return true if you were able to give each customer the correct change, otherwise return false.
Example 1:
Input: bills = [5,5,5,5,10,20]
Output: true
Explanation:
For the first 3 customers, we collect 3 $5 bills in that order.
For the 4th customer, we collect a $10 bill and give back $5.
For the fifth customer, we returned a $10 bill and a $5 bill.
Since all customers got the correct change, we output true.
Example 2:
Input: bills = [5,5,10,10,20]
Output: false
Explanation:
For the first 2 customers, we collect 2 $5 bills in that order.
For the next 2 customers, we collect a $10 bill and give back $5.
For the last customer, we can't return the $15 because we only have two $10 bills right now.
Since not every customer received the correct change, the answer is false.
Tip:
1 <= <= 10^5
bills[i] is either 5, 10 or 20.
Thoughts:
Adopt a greedy mindset:
This question may be a little confusing when you first look at it - how is this going to make change to ensure that you complete all of your bills?
But a closer look reveals that there is very little room for us to make judgments!
There are only three amounts of quantities to maintain, 5, 10 and 20.
There are three scenarios as follows:
Scenario 1: The bill is 5. Just take it.
Scenario 2: Bill is 10, consume a 5, add a 10
Scenario 3: Bill is 20, prioritize consumption of one 10 and one 5, and if that is not enough, consume three more 5s
At this point, we will find that Case 1, Case 2, are fixed strategies, do not need to do our analysis, and the only uncertainty is actually in Case 3.
And while the logic of case 3 is not complicated or even feels like pure simulation would work, there is actually greed here in case 3.
Why prioritize the consumption of a 10 and a 5 when the bill is 20?
Because Dollar 10 can only make change for Bill 20, and Dollar 5 can make change for both Bill 10 and Bill 20, Dollar 5 is more versatile!
So local optimal: when bill 20 is encountered, prioritize the consumption of $10 to complete this change. Global optimum: make change for all bills.
A local optimum can be introduced as a global optimum and no counterexample can be found, so try the greedy algorithm!
Ideas to learn:/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%#%E6%80%9D%E8%B7%AF
C++ code example
```cpp
class Solution {
public.
bool lemonadeChange(vector<int>& bills) {
int five=0,ten=0;
for(auto bill:bills){
// just take the five bucks
if(bill==5) five++;
//Ten, see if there is any five dollar change, if not, just return false
else if(bill==10){
if(five>=1) five--,ten++;
else return false.
}
// For twenty blocks, prioritize consuming a 10-fast and a 5-block. If not, see if there are three 5-blockers.
//If there are still none, return false
else if(bill==20){
if(ten>=1&&five>=1){
five--;ten--;
}
else if(five>=3) five--=3;
else return false; } else if(five>=3)
}
}
return true; }
}
}; }