মান ল করুন nums নামের একটি সংখ্যার তালিকা এবং size, k নামে দুটি মান। এখন একটি অপারেশন আছে যেখানে size দৈর্ঘ্যের একটি কন্টিগুয়াস সাবলিস্ট নিয়ে প্রতিটি এলিমেন্ট ১ করে বাড়ানো যায়। এই অপারেশন k বার করা যাবে, nums-এ সম্ভাব্য সর্বোচ্চ মিনিমাম ভ্যালু খুঁজে বের করতে হবে।
যদি ইনপুট হয় nums = [2, 5, 2, 2, 7], size = 3, k = 2, তবে আউটপুট হবে ৩, কারণ [2, 5, 2] ইনক্রিমেন্ট করলে [3, 6, 3, 2, 7], তারপর [6, 3, 2] ইনক্রিমেন্ট করলে [3, 7, 4, 3, 7], মিনিমাম ৩।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- একটি possible() ফাংশন সংজ্ঞায়িত করুন। এটি target গ্রহণ করবে।
- events := N আকারের একটি তালিকা, ০ দিয়ে ভরা
- moves := 0, s := 0
- i কে ০ থেকে 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
