मान लीजिए एक जूते की दुकान में n अलग-अलग जूते हैं जिनके विभिन्न आकार size नामक सरणी में मौजूद हैं और m ग्राहकों के लिए जोड़ों की एक और सूची demand दी गई है, जहां demand[i] में (shoe_size, money) होता है इसलिए demand i वाला ग्राहक उस जूते की मांग करता है जिसका आकार shoe_size है और वह दी गई राशि का भुगतान कर सकता है। हमें यह पता लगाना है कि दुकानदार इन जूतों को बेचकर कितना पैसा कमा सकता है।
उदाहरण के लिए, यदि इनपुट 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 होगा क्योंकि:
- पहला ग्राहक आकार 6 का जूता 55 की कीमत पर खरीदेगा
- दूसरा ग्राहक आकार 6 का जूता 45 की कीमत पर खरीदेगा
- स्टॉक में आकार 6 का कोई जूता नहीं है
- चौथा ग्राहक आकार 4 का जूता 40 की कीमत पर खरीदेगा
- पांचवां ग्राहक आकार 18 का जूता 60 की कीमत पर खरीदेगा
- छठा ग्राहक जूता नहीं पाएगा क्योंकि आकार 10 का कोई जूता नहीं है
कुल कमाई 55 + 45 + 40 + 60 = 200।
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- n := demand का आकार
- sizes := आकार के आधार पर जूतों की आवृत्तियों वाला मैप
- earn := 0
- i के लिए 0 से n - 1 तक की रेंज में, करें
- (sz, price) := demand[i]
- यदि आकार sz का जूता sizes में मौजूद है, तो
- sizes[sz] := sizes[sz] - 1
- earn := 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