C++ प्रोग्राम n पूर्णांक युग्मों में न्यूनतम अंतर मान ज्ञात करने के लिए

मान लीजिए, हमें दो एरे ए और बी दिए गए हैं जिनमें क्रमशः कुल 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}