极客教程C++ 检查 X 是否能给队列中的每个人找零
给定一个整数数组 Ai，表示第 i 个人所持有的钞票。可能的货币种类为 5、10 和 20。所有 n 个人都站在队列中等待从 X 那里购买价值 5 印度卢比的冰淇淋。最初，X 的初始余额为 0。检查 X 是否能够为所有等待购买冰淇淋的人提供找零。
示例：
输入： a[] = {5, 5, 5, 10, 20}
输出： YES
当第四个人来购买冰淇淋时，X 有三个 5 印度卢比的零钱，因此 X 给了他 1 个，现在当第五个人来购买冰淇淋时，X 有两个 5 印度卢比和一张 10 印度卢比的钞票，因此他给了他一张 10 印度卢比和一张 5 印度卢比的钞票。
输入： a[] = {5, 10, 10, 20}
输出： NO
解决该问题的方法是跟踪 Rs 5 和 Rs 10 货币的数量。Rs 20 货币将不会被使用，因为这是一个人可以给的最高货币，因此不能作为找零。初始化两个变量来计算 Rs 5（fiveCount）和 Rs 10（tenCount）。如果人有 Rs 10 货币且 fiveCount > 0，则减少 fiveCount 并增加 tenCount。如果 X 没有 Rs 5，则 X 无法给该人所需的找钱。如果该人有 5 美元的纸币，则将 fiveCount 增加一。如果该人持有 Rs 20，则将有三个条件：
- 如果 fiveCount > 0 且 tenCount > 0，那么将两者都减少。
- 否则，如果 fiveCount >= 3，则将 fivecount 减少三个。
- 否则，返回 false。
如果队列中的所有人都能找到零钱，则打印 “YES”，否则打印“NO”。
以下是上述思路的实现。
// C++ program to check whether X can give change
// to every person in the Queue
#include <bits/stdc++.h>
using namespace std;
// Function to check if every person will
// get the change from X
int isChangeable(int notes[], int n)
{
// To count the 5and 10& notes
int fiveCount = 0;
int tenCount = 0;
// Serve the customer in order
for (int i = 0; i note by one
if (notes[i] == 5)
fiveCount++;
else if (notes[i] == 10) {
// decrease the number of note 5and
// increase 10 note by one
if (fiveCount > 0) {
fiveCount--;
tenCount++;
}
else
return 0;
}
else {
// decrease 5and 10 note by one
if (fiveCount > 0 && tenCount >0) {
fiveCount--;
tenCount--;
}
// decrease 5$ note by three
else if (fiveCount >= 3) {
fiveCount -= 3;
}
else
return 0;
}
}
return 1;
}
// Driver Code
int main()
{
// queue of customers with available notes.
int a[] = { 5, 5, 5, 10, 20 };
int n = sizeof(a) / sizeof(a[0]);
// Calling function
if (isChangeable(a, n))
cout << "YES";
else
cout << "NO";
return 0;
}
// Java程序检查X是否能给队列中的每个人找零
import java.io.*;
class GFG
{
// 检查每个人是否能从X那里得到找零
static int isChangeable(int notes[],
int n)
{
// 计算5美元和10美元的数量
int fiveCount = 0;
int tenCount = 0;
// 按顺序为顾客提供服务
for (int i = 0; i < n; i++)
{
// 将5美元的数量增加1
if (notes[i] == 5)
fiveCount++;
else if (notes[i] == 10)
{
// 将5美元的数量减少1，将10美元的数量增加1
if (fiveCount > 0)
{
fiveCount--;
tenCount++;
}
else
return 0;
}
else
{
// 将5美元和10美元的数量减少1
if (fiveCount > 0 &&
tenCount > 0)
{
fiveCount--;
tenCount--;
}
// 将5美元的数量减少3
else if (fiveCount >= 3)
{
fiveCount -= 3;
}
else
return 0;
}
}
return 1;
}
// 主函数
public static void main (String[] args)
{
// 包含可用钞票的顾客队列
int a[] = {5, 5, 5, 10, 20};
int n = a.length;
// 调用函数
if (isChangeable(a, n) > 0)
System.out.print("YES");
else
System.out.print("NO");
}
}
# Python程序检查X是否能给队列中的每个人找零
# 检查每个人是否能从X那里得到找零
def isChangeable(notes, n):
# 计算5美元和10美元的数量
fiveCount = 0
tenCount = 0
# 按顺序为顾客提供服务
for i in range(n):
# 将5美元的数量增加1
if (notes[i] == 5):
fiveCount += 1
elif(notes[i] == 10):
# 将5美元的数量减少1，将10美元的数量增加1
if (fiveCount > 0):
fiveCount -= 1
tenCount += 1
else:
return 0
else:
# 将5美元和10美元的数量减少1
if (fiveCount > 0 and tenCount > 0):
fiveCount -= 1
tenCount -= 1
# 将5美元的数量减少3
elif (fiveCount >= 3):
fiveCount -= 3
else:
return 0
return 1
# 主程序
# 包含可用钞票的顾客队列
a = [5, 5, 5, 10, 20 ]
n = len(a)
# 调用函数
if (isChangeable(a, n)):
print("YES")
else:
print("NO")
# 本代码由PrinciRaj1992贡献
// C#程序，用于检查X是否可以给队列中的每个人找钱
using System;
class GFG
{
// 检查是否每个人都能从X那里找到零钱
static int isChangeable(int []notes,
int n)
{
// 统计5元纸币和10元纸币的数量
int fiveCount = 0;
int tenCount = 0;
// 按顺序为顾客服务
for (int i = 0; i < n; i++)
{
// 5元纸币数量加一
if (notes[i] == 5)
fiveCount++;
else if (notes[i] == 10)
{
// 减少5元纸币数量并增加10元纸币数量
if (fiveCount > 0)
{
fiveCount--;
tenCount++;
}
else
return 0;
}
else
{
// 减少5元和10元纸币数量
if (fiveCount > 0 &&
tenCount > 0)
{
fiveCount--;
tenCount--;
}
// 减少3张5元纸币
else if (fiveCount >= 3)
{
fiveCount -= 3;
}
else
return 0;
}
}
return 1;
}
// 主函数
public static void Main ()
{
// 顾客的队列及其可用纸币。
int []a = {5, 5, 5, 10, 20};
int n = a.Length;
// 调用函数
if (isChangeable(a, n) > 0)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
<script>
// Javascript程序，用于检查X是否可以给队列中的每个人找钱
// 检查是否每个人都能从X那里找到零钱
function isChangeable(notes, n)
{
// 统计5元纸币和10元纸币的数量
let fiveCount = 0;
let tenCount = 0;
// 按顺序为顾客服务
for (let i = 0; i < n; i++)
{
// 5元纸币数量加一
if (notes[i] == 5)
fiveCount++;
else if (notes[i] == 10)
{
// 减少5元纸币数量并增加10元纸币数量
if (fiveCount > 0)
{
fiveCount--;
tenCount++;
}
else
return 0;
}
else
{
// 减少5元和10元纸币数量
if (fiveCount > 0 &&
tenCount > 0)
{
fiveCount--;
tenCount--;
}
// 减少3张5元纸币
else if (fiveCount>= 3)
{
fiveCount -= 3;
}
else
return 0;
}
}
return 1;
}
// 顾客的队列及其可用纸币。
let a = [5, 5, 5, 10, 20];
let n = a.length;
// 调用函数
if (isChangeable(a, n) > 0)
document.write("YES");
else
document.write("NO");
</script>
输出结果
YES
性能分析：
时间复杂度： O(n)。
空间复杂度： O(1)。