मान लीजिए, हमें दो ऐरे a और b दिए गए हैं जिनमें क्रमशः n और m मान हैं। हमें दो ऐरे से मानों का उपयोग करके n या m संख्या के युग्म (जो भी न्यूनतम है) बनाने हैं। एक युग्म में ऐरे a से एक मान और ऐरे b से दूसरा मान होना चाहिए। हमें युग्मों को इस तरह बनाना है ताकि युग्म में मानों का अंतर न्यूनतम और समान हो। हम मान को आउटपुट के रूप में प्रिंट करते हैं।
उदाहरण के लिए, यदि इनपुट n = 4, m = 4, a = {2, 3, 4, 7}, b = {3, 4, 6, 5} है, तो आउटपुट 1 होगा।
बनाए जा सकने वाले युग्म हैं:
(3, 4), (4, 5), (7, 6), (2, 3).
सभी युग्मों में मानों का अंतर 1 है।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
ऐरे a को सॉर्ट करें 0 से प्रारंभ एक ऐरे s1 परिभाषित करें 0 से प्रारंभ एक ऐरे s2 परिभाषित करें i := 1 से n-1 तक, i := i + 2, करें: s1 के अंतिम तत्व + a[i] - a[i - 1] को s1 के अंत में डालें i := 2 से n-1 तक, i := i + 2, करें: s2 के अंतिम तत्व + a[i] - a[i - 1] को s2 के अंत में डालें ans := infinity b के प्रत्येक मान w के लिए, करें: diff := w से कम नहीं ऐरे a में पहला तत्व - a का पहला मान sub := s1[diff / 2] का अंतिम तत्व + s2 ans := ans और 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} आउटपुट
1
