มี Array notes แทนธนบัตรลูกค้าในคิว (50, 100, 200) ตั๋วราคา 50 เริ่มต้นเงินทอน 0 ต้องเช็คว่าขายตั๋วตามลำดับได้หมดหรือไม่
เช่น Input notes = [50, 50, 100, 100] Output True (50,50 ไม่ต้องทอน; 100,100 ทอน 50 แต่ละใบ)
ขั้นตอนแก้ (Greedy):
- เก็บ Count ของ 50 และ 100
- ลูกค้า 50: count50++
- ลูกค้า 100: ต้องมี 50 อย่างน้อย 1 -> count50--, count100++
- ลูกค้า 200: พยายามทอน 100+50 ก่อน ไม่งั้น 50x3
ตัวอย่างโค้ด
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:
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
if i == len(notes):
return True
return False
notes = [50, 50, 100, 100]
print(solve(notes))
Input
[50, 50, 100, 100]
Output
True
