在柠檬水摊上,每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。 每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。 你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。注意,一开始你手头没有任何零钱。 如果你能给每位顾客正确找零,返回 true ,否则返回 false 。
示例 1: 输入:[5,5,5,10,20] 输出:true
思路:
设置两个变量 five_count
和 ten_count
分别表示手里拥有的 5 美元和 10 美元的数量,初始值都为 0。
遍历每个顾客支付的金额,如果是 5 美元,则不需要找零;如果是 10 美元,则需要找回 5 美元;如果是 20 美元,则需要找回 15 美元。
对于 10 美元的找零,我们需要首先判断手里是否有足够的 5 美元来找零。如果有,则将 five_count
减 1,将 ten_count
加 1;如果没有,则无法找零,返回 false
。
对于 20 美元的找零,我们需要优先使用一张 10 美元和一张 5 美元来找零,因为这样可以让手里的 5 美元硬币更多,以备后续使用。如果手里没有足够的 10 美元和 5 美元,则可以使用三张 5 美元来找零。如果无法找零,返回 false
。
如果所有顾客的交易都能正确找零,最终返回 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;
}
更多【编程技术-贪心法之柠檬水找零】相关视频教程:www.yxfzedu.com