ধরুন একটি জুতাদোকানে nটি ভিন্ন সাইজের জুতা আছে size অ্যারেতে এবং 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 কারণ:
- প্রথম কাস্টমার সাইজ ৬ এর জুতা ৫৫ টাকায় কিনবে
- দ্বিতীয় কাস্টমার সাইজ ৬ এর জুতা ৪৫ টাকায় কিনবে
- স্টকে আর সাইজ ৬ এর জুতা নেই
- চতুর্থ কাস্টমার সাইজ ৪ এর জুতা ৪০ টাকায় কিনবে
- পঞ্চম কাস্টমার সাইজ ১৮ এর জুতা ৬০ টাকায় কিনবে
- ষষ্ঠ কাস্টমারকে জুতা মেলবে না কারণ সাইজ ১০ নেই
মোট আয় 55 + 45 + 40 + 60 = 200।
সমাধানের ধাপসমূহ
n := size of demandsizes := Counter(shoes)- সাইজ অনুযায়ী জুতার ফ্রিকোয়েন্সিearn := 0for i in range 0 to n-1:(sz, price) := demand[i]- যদি সাইজ
szএর জুতাsizes-এ থাকে, তবে:sizes[sz] -= 1earn += 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
