মান লিখুন: আমাদের কাছে দুটি অ্যারে 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).
সব জোড়ার পার্থক্য ১।
সমাধানের ধাপসমূহ
a সর্ট করুন
s1 অ্যারে ০ দিয়ে ইনিশিয়ালাইজ
s2 অ্যারে ০ দিয়ে ইনিশিয়ালাইজ
for i := 1 থেকে n-1, i += 2:
s1-এ s1.back() + a[i] - a[i-1] পুশ করুন
for i := 2 থেকে n-1, i += 2:
s2-এ s2.back() + a[i] - a[i-1] পুশ করুন
ans := infinity
b-এর প্রতিটি w এর জন্য:
diff := a-তে w-র চেয়ে বড় বা সমান প্রথম এলিমেন্টের ইনডেক্স - a[0]
sub := s1[diff/2] + s2.back() - s2[diff/2] + abs(a[diff/2*2] - w)
ans := min(ans, sub)
ans প্রিন্ট করুন
C++ বাস্তবায়ন
#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
