n পূর্ণসংখ্যা জোড়ায় ন্যূনতম পার্থক্য মান খুঁজে বের করতে C++ প্রোগ্রাম

ধরুন, আমাদেরকে a এবং b দুটি অ্যারে দেওয়া হয়েছে যেগুলির মধ্যে যথাক্রমে n এবং m মান রয়েছে। আমাদের দুটি অ্যারে থেকে মান ব্যবহার করে জোড়ার n বা m সংখ্যা (যেটি সর্বনিম্ন) তৈরি করতে হবে। একটি জোড়াতে অবশ্যই একটি অ্যারে থেকে একটি মান থাকতে হবে এবং অ্যারের বি থেকে আরেকটি মান থাকতে হবে। আমাদের জোড়াগুলি এমনভাবে তৈরি করতে হবে যাতে জোড়াগুলির মানের পার্থক্য ন্যূনতম এবং একই থাকে। আমরা আউটপুট হিসাবে মান প্রিন্ট করি।

সুতরাং, যদি ইনপুট হয় n =4, m =4, a ={2, 3, 4, 7}, b ={3, 4, 6, 5}, তাহলে আউটপুট হবে 1।

যে জোড়াগুলি তৈরি করা যায় তা হল −

(3, 4), (4, 5), (7, 6), (2, 3).

সমস্ত জোড়ায় মানের পার্থক্য হল 1.

পদক্ষেপ

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

sort the array a
Define an array s1 initialized with 0
Define an array s2 initialized with 0
for initialize i := 1, when i < n, update i := i + 2, do:
   insert last element of s1 + a[i] - a[i - 1] at the end of s1
for initialize i := 2, when i < n, update i := i + 2, do:
   insert last element of s2 + a[i] - a[i - 1] at the end of s2
ans := infinity
for each value w in b, do:
   diff := first element in the array a not less than w - first value of a
   sub := last element of s1[diff / 2] + s2
   ans := minimum of ans and sub
print(ans)

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int n, int m, vector<int> a, vector<int> b){
   sort(a.begin(), a.end());
   vector<int> s1 = {0};
   vector<int> s2 = {0};
   for (int i = 1; i < n; i += 2)
      s1.push_back(a[i] - a[i - 1] + s1.back());
   for (int i = 2; i < n; i += 2)
      s2.push_back(a[i] - a[i - 1] + s2.back());
   int ans = INF;
   for (const auto & w : b) {
      int diff = lower_bound(a.begin(), a.end(), w) - a.begin();
      int sub = s1[diff / 2] + s2.back() - s2[diff / 2] + abs(a[diff / 2 * 2] - w);
      ans = min(ans, sub);
   }
   cout << ans << endl;
}
int main() {
   int n = 4, m = 4;
   vector<int> a = {2, 3, 4, 7}, b = {3, 4, 6, 5};
   solve(n, m, a, b);
   return 0;
}

ইনপুট

4, 4, {2, 3, 4, 7}, {3, 4, 6, 5}