目录
题目概述：
解题思路：
具体代码：
总结：
题目概述：
在柠檬水摊上，每个柠檬水售价 5 元。客户正在排队向您购买，并且一次订购一份柠檬水。
每位顾客只会购买一份柠檬水，并支付 5 元、10 元或 20 元的面额。您必须向每位客户提供正确的零钱，以便客户支付 5 元的净交易。
当且仅当您可以为每个客户提供正确的更改时才返回 True 否则返回 False
输入输出格式
输入格式
输入的形式采用字符串的形式例如: 5 5 10 10 20 而 test_str 用于接收这些字符并做后续处理。
输出格式
输出的形式是以字符串的形式如果能成功的找散客人的钱则返回 True 否则 False 。
输入输出样例1
输入
5 5 5 10 20
输出
True
解释
输入的部分表示排队购买柠檬水的客人的金钱面额，如果柠檬水摊能找散这些金额则返回 True 。
输入输出样例2
输入
5 5 10 10 20
输出
False
说明提示
一开始你是没有任何一张钱的，你只能从按照顺序赚取的钱去找散客人。
解题思路：
这道题的核心思路是贪心算法，对于收银员来说，我们不需要统计目前位置收到的20元钞票，因为一杯柠檬水售价只有5元，而纸钞只有三种，分别是5元，10元，20元。无论如何找零，收银员都用不到20元的钞票，如果客人使用5元纸钞则不需要找零，如果客人使用10元纸钞则需要使用5元纸钞找零，如果客人使用20元纸钞则需要3张5元纸钞或者一张5元纸钞和一张10元纸钞。
所以我们只需要分别统计好为每一个客人找零时手上持有的5元和10元纸钞数量。由以上分析可知找零时5元纸钞使用率最高，所以不是没有办法的情况下不要使用5元纸钞。
具体代码：
#include<stdio.h>
int main(void)
{int n1 = 0;//5元纸钞的数量int n2 = 0;//10元纸钞的数量int num;//当前客人手持的钞票int flag = 0;while (scanf("%d", &num) != EOF){if (num == 5)n1++;//如果客人带的是5元钞票则5元钞票数量增加1并且不需要找零else if (num == 10){if (n1 > 0){n1--;n2++;//如果客人带的是10元钞票则10元钞票数量增加1，找零一张5元纸钞}else{flag = 1;//如果没有5元纸钞的话无法找零，退出循环。break;}}else{if (n2 > 0 && n1 > 0){n1--;n2--;//如果是20元纸钞，并且收银员有10元纸钞和5元纸钞，则用这两种钞票找零}else if (n1 >= 3){n1 -= 3;//如果只有5元钞票并且可以找零，用掉三张5元钞票。}else{flag = 1;//如果无法找零退出循环。break;}}}if (flag)printf("False");elseprintf("True");
}总结：
该题目类型属于贪心算法，贪心算法的本质是通过所有的局部最优解结合来找到全局最优解，可以理解成“能多吞一点是一点”，而我们这道题贪的是5元钞票的数量，不到万不得已，能不用则不用。
)
