#1538. 柠檬水找零问题

柠檬水找零问题

故事背景

在一家柠檬水摊前,顾客们排成队购买柠檬水。每杯柠檬水的价格是5元。顾客们用5元、10元和20元的纸币支付。由于摊位刚开始营业,没有任何零钱。作为摊主,你需要判断是否能够给每一位顾客正确找零,使得每笔交易都能顺利完成。

题目描述

在柠檬水摊上,每杯柠檬水的售价为5元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你支付5元、10元或20元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付5元。

注意,一开始你手头没有任何零钱。

如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

输入格式

第一行输入一个整数 n ( 1n10001 \leq n \leq 1000 ),表示顾客的数量。

第二行输入 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元的用途更广泛
  • 注意处理各种边界情况