मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और दो मान, size और k हैं। अब मान लीजिए एक ऑपरेशन है जहां हम लंबाई size की एक सन्निकट सबलिस्ट लेते हैं और प्रत्येक तत्व को एक से बढ़ाते हैं। हम इस ऑपरेशन को k बार कर सकते हैं, हमें nums में संभव सबसे बड़ा न्यूनतम मान ढूंढना है।
इसलिए, यदि इनपुट nums = [2, 5, 2, 2, 7], size = 3, k = 2 जैसा है, तो आउटपुट 3 होगा, क्योंकि हम [2, 5, 2] को बढ़ाकर [3, 6, 3, 2, 7] प्राप्त कर सकते हैं और फिर [6, 3, 2] को बढ़ाकर [3, 7, 4, 3, 7] प्राप्त कर सकते हैं, न्यूनतम 3 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- एक फ़ंक्शन possible() परिभाषित करें। यह target लेगा
- events := आकार N की एक सूची, और 0 से भरें
- moves := 0, s := 0
- i के लिए 0 से N तक की रेंज में, करें
- s := s + events[i]
- delta := target - (A[i] + s)
- यदि delta > 0, तो
- moves := moves + delta
- s := s + delta
- यदि i + size < N, तो
- events[i + size] := events[i + size] - delta
- यदि moves <= K तो true वापस करें
- मुख्य विधि से, निम्नलिखित करें
- N := A का आकार
- left := 0, right := 10^10
- जब तक left < right, करें
- mid := (left + right + 1) / 2
- यदि possible(mid), तो
- left := mid
- अन्यथा,
- right := mid - 1
- left वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
class Solution: def solve(self, A, size, K): N = len(A) def possible(target): events = [0] * N moves = s = 0 for i in range(N): s += events[i] delta = target - (A[i] + s) if delta > 0: moves += delta s += delta if i + size < N: events[i + size] -= delta return moves <= K left, right = 0, 10 ** 10 while left < right: mid = (left + right + 1)//2 if possible(mid): left = mid else: right = mid - 1 return left ob = Solution() nums = [2, 5, 2, 2, 7] size = 3 k = 2 print(ob.solve(nums, size, k))
इनपुट
[2, 5, 2, 2, 7], 3, 2
आउटपुट
3
