मान लीजिए एक कैंडी स्टोर है जहां N विभिन्न प्रकार की कैंडीज उपलब्ध हैं और सभी N विभिन्न प्रकार की कैंडीज की कीमतें दी गई हैं। स्टोर एक आकर्षक ऑफर भी प्रदान करता है। इस ऑफर के अनुसार, हम स्टोर से एक कैंडी खरीद सकते हैं और अधिकतम K अन्य विभिन्न प्रकार की कैंडीज मुफ्त में प्राप्त कर सकते हैं। हमें सभी N विभिन्न प्रकार की कैंडीज खरीदने के लिए खर्च की जाने वाली न्यूनतम राशि ढूंढनी है। हमें सभी N विभिन्न प्रकार की कैंडीज खरीदने के लिए खर्च की जाने वाली अधिकतम राशि भी ढूंढनी है। दोनों मामलों में हमें ऑफर का उपयोग करना होगा और अधिकतम संभव कैंडीज वापस प्राप्त करनी होंगी। यदि k या अधिक कैंडीज उपलब्ध हैं, तो हमें हर कैंडी खरीद पर k कैंडीज चुननी होंगी। लेकिन, यदि k से कम कैंडीज उपलब्ध हैं, तो हमें एक कैंडी खरीद पर सभी कैंडीज चुननी होंगी।
तो, यदि इनपुट price = [4, 3, 2, 5] और k = 2 जैसा है, तो आउटपुट होगा: न्यूनतम = 5 और अधिकतम = 9। ऐसा इसलिए है क्योंकि जब k 2 है, यदि हम एक कैंडी खरीदते हैं तो हम अधिकतम दो और मुफ्त में ले सकते हैं। पहले मामले में हम 2 रुपये की कैंडी खरीद सकते हैं और 4 और 5 रुपये की कैंडीज मुफ्त ले सकते हैं, साथ ही हम 3 रुपये की कैंडी भी खरीद सकते हैं, तो न्यूनतम लागत = 2 + 3 = 5। दूसरी ओर, दूसरे मामले में हम 5 रुपये की कैंडी खरीदते हैं और 2 और 3 रुपये की कैंडीज मुफ्त लेते हैं, या हम 4 रुपये की कैंडी भी खरीद सकते हैं। तो, अधिकतम लागत = 4 + 5 = 9।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
get_min() फंक्शन परिभाषित करें। यह A, k लेगा।
n := A का आकार
सूची A को सॉर्ट करें
res := 0, i := 0
जब n शून्येतर है, करें:
res := res + A[i]
n := n - k
i := i + 1
res लौटाएं
get_max() फंक्शन परिभाषित करें। यह A, k लेगा।
n := A का आकार
सूची A को सॉर्ट करें
res := 0, idx := 0
i := n-1
जब i >= idx, करें:
res := res + A[i]
idx := idx + k
i := i - 1
res लौटाएं
मुख्य विधि से इन दो फंक्शन्स को कॉल करके परिणाम प्राप्त करें
get_min(A, k)
get_max(A, k)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def get_min(A,k): n = len(A) A.sort() res = 0 i=0 while(n): res += A[i] n = n-k i += 1 return res def get_max(A, k): n = len(A) A.sort() res = 0 idx = 0 i=n-1 while(i>=idx): res += A[i] idx += k i -= 1 return res A = [4, 3, 2, 5] k = 2 print(get_min(A, k),get_max(A, k))
इनपुट
[4, 3, 2, 5], 2
आउटपुट
5 9
