#1538. 柠檬水找零问题
柠檬水找零问题
故事背景
在一家柠檬水摊前,顾客们排成队购买柠檬水。每杯柠檬水的价格是5元。顾客们用5元、10元和20元的纸币支付。由于摊位刚开始营业,没有任何零钱。作为摊主,你需要判断是否能够给每一位顾客正确找零,使得每笔交易都能顺利完成。
题目描述
在柠檬水摊上,每杯柠檬水的售价为5元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你支付5元、10元或20元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付5元。
注意,一开始你手头没有任何零钱。
如果你能给每位顾客正确找零,返回 true ,否则返回 false 。
输入格式
第一行输入一个整数 n ( ),表示顾客的数量。
第二行输入 n 个整数,表示每位顾客支付的金额,只能是5、10或20。
输出格式
输出一个布尔值,表示是否能够给每位顾客正确找零。如果能,输出 true ;否则,输出 false 。
样例输入 1
5
5 5 5 10 20
样例输出 1
true
样例输入 2
5
5 5 10 10 20
样例输出 2
false
样例输入 3
3
10 10 5
样例输出 3
false
提示
- 这是一个经典的贪心算法问题
- 注意维护5元和10元的数量,因为20元无法用来找零
- 对于20元的支付,优先使用10元+5元的组合找零,因为5元的用途更广泛
- 注意处理各种边界情况