প্রথম এবং শেষ দিক থেকে জোড়া তৈরি করার জন্য প্রয়োজনীয় সংখ্যক অপারেশন খুঁজে বের করার প্রোগ্রামটি পাইথনে একই যোগফলের সাথে রয়েছে

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। এই তালিকার দৈর্ঘ্য সমান। এখন একটি ক্রিয়াকলাপ বিবেচনা করুন যেখানে আমরা সংখ্যায় যেকোনো সংখ্যা নির্বাচন করি এবং পরিসীমা [1 এবং সর্বাধিক সংখ্যা] এর মান সহ আপডেট করি। আমাদের এই ধরনের ন্যূনতম সংখ্যক ক্রিয়াকলাপগুলি খুঁজে বের করতে হবে যাতে প্রতিটি i, nums[i] + nums[n-1-i] একই সংখ্যার সমান হয়৷

সুতরাং, যদি ইনপুটটি nums =[8,6,2,5,9,2] এর মত হয়, তাহলে আউটপুট হবে 2, কারণ যদি আমরা nums[2]-এ প্রথম 2 কে 5 এ পরিবর্তন করি এবং 9 এ nums[4] ] থেকে 4, তারপর উপাদানগুলি হবে [8,6,5,5,4,2], তারপর প্রতিটি i-এর জন্য nums[i] + nums[n-1-i] হবে (8+2) =( 6+4) =(5+5) =10।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

N :=সংখ্যার আকার
mx :=সংখ্যার সর্বোচ্চ
ইভেন্ট :=একটি নতুন তালিকা
idx :=0
যখন idx <ফ্লোর অফ N / 2, do
- a :=nums[idx]
- b :=সংখ্যা[N - idx - 1]
- ইভেন্টের শেষে একটি জোড়া (সর্বনিম্ন (a + 1), (b + 1), 1) সন্নিবেশ করান
- ইভেন্টের শেষে একটি জোড়া (a + b, 1) ঢোকান
- ইভেন্টের শেষে একটি জোড়া (a + b + 1, -1) ঢোকান
- ইভেন্টের শেষে একটি জোড়া (সর্বোচ্চ (a + mx) এবং (b + mx + 1), -1) সন্নিবেশ করান
- idx :=idx + 1
তালিকা ইভেন্টগুলি সাজান
বর্তমান :=0
mx_same :=0
ইভেন্টে প্রতিটি জোড়ার (ইভেন্ট, ডেল্টা) জন্য, করুন
- কারেন্ট :=বর্তমান + ডেল্টা
- mx_same :=বর্তমানের সর্বাধিক এবং mx_same
প্রত্যাবর্তন N - mx_same

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(nums):
   N = len(nums)
   mx = max(nums)
   events = []

   idx = 0
   while idx < N // 2:
      a = nums[idx]
      b = nums[N - idx - 1]

      events.append((min(a + 1, b + 1), 1))
      events.append((a + b, 1))
      events.append((a + b + 1, -1))
      events.append((max(a + mx, b + mx) + 1, -1))

   idx += 1

   events.sort()
   current = 0
   mx_same = 0

   for event, delta in events:
      current += delta
      mx_same = max(current, mx_same)

   return N - mx_same

nums = [8,6,2,5,9,2]
print(solve(nums))

ইনপুট

[6, 8, 5, 2, 3]