Bài toán: Khách hàng mua vé 50đ, trả tiền 50/100/200. Ban đầu không có tiền lẻ. Kiểm tra có phục vụ hết hàng đợi theo thứ tự không.
Quy tắc trả tiền
- Khách trả 50: không cần trả lẻ, giữ 50.
- Khách trả 100: phải trả 50 (cần có ít nhất 1 tờ 50).
- Khách trả 200: ưu tiên trả 100+50 (giữ lại 50 cho khách sau), nếu không thì trả 3×50.
Triển khai Python
from collections import defaultdict
def solve(notes):
freq = defaultdict(int)
i = 0
while i < len(notes):
if notes[i] == 50:
freq[50] += 1
elif notes[i] == 100:
freq[100] += 1
if freq[50] == 0:
break
freq[50] -= 1
else: # 200
if freq[100] > 0 and freq[50] > 0:
freq[100] -= 1
freq[50] -= 1
elif freq[50] >= 3:
freq[50] -= 3
else:
break
i += 1
return i == len(notes)
# Test
print(solve([50, 50, 100, 100])) # True
print(solve([50, 100, 200])) # True: 50→giữ, 100→trả 50, 200→trả 100+50? Không có 100. freq[50]=0 → False
# Wait: [50,100,200]: step1: freq[50]=1. step2: freq[100]=1, freq[50]=0. step3: 200, freq[100]=1>0 but freq[50]=0, freq[50]>=3? No. → break → False.
print(solve([50, 50, 50, 100, 200])) # True: 3x50, 100→trả 50 (2 left), 200→trả 3x50? No, 2<3. But freq[100]=1, freq[50]=2 → 100+50 OK.
Kết quả
True
Giải thích
- Duyệt hàng đợi, cập nhật tần suất tiền lẻ trên tay.
- Với 200: ưu tiên trả 100+50 (giúp giữ tiền 50 cho khách 100 sau).
- Nếu không thể trả lẻ tại bất kỳ bước nào → break, trả False.
- Độ phức tạp: O(n) time, O(1) space (chỉ 3 loại tiền).