สมมติว่าในร้านรองเท้ามี n คู่ขนาดต่างๆ อยู่ในอาเรย์ shoes และมีรายการลูกค้า m คนใน demand โดย demand[i] = (shoe_size, money) หมายถึงลูกค้าคนที่ i ต้องการรองเท้าขนาด shoe_size และจ่าย money เราต้องหาเงินที่ร้านได้จากการขาย
ตัวอย่าง shoes = [2,3,4,5,6,8,7,6,5,18] demand = [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)] ผลลัพธ์ = 200
ขั้นตอนการแก้ปัญหา
- n := ขนาดของ demand
- sizes := Counter ของ shoes (นับจำนวนแต่ละขนาด)
- earn := 0
- for i ในช่วง 0 ถึง n-1:
- (sz, price) := demand[i]
- ถ้าขนาด sz ยังมีใน sizes: sizes[sz] -= 1, earn += price
- คืนค่า earn
ตัวอย่างโค้ด
from collections import Counter
def solve(shoes, demand):
n = len(demand)
sizes = Counter(shoes)
earn = 0
for i in range(n):
sz, price = demand[i]
if sizes[sz]:
sizes[sz] -= 1
earn += price
return earn
shoes = [2,3,4,5,6,8,7,6,5,18]
demand = [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]
print(solve(shoes, demand))
อินพุต
[2,3,4,5,6,8,7,6,5,18], [(6,55), (6,45), (6,55), (4,40), (18,60), (10,50)]
เอาต์พุต
200
