ধরুন আমাদের দুটি অ্যারে রয়েছে A এবং B উভয়ই N উপাদান সহ। N কম্পিউটার এবং N সকেট আছে বিবেচনা করুন. ith কম্পিউটারের স্থানাঙ্ক হল A[i] এবং ith সকেটের স্থানাঙ্ক হল b[i]। এই 2N স্থানাঙ্কগুলি জোড়া-ভিত্তিক স্বতন্ত্র। আমরা প্রতিটি কম্পিউটারকে তারের দ্বারা একটি সকেটের সাথে সংযুক্ত করতে চাই। প্রতিটি সকেট সর্বাধিক একটি কম্পিউটারে সংযুক্ত করা যেতে পারে। আমরা কত উপায়ে তারের দৈর্ঘ্য কমাতে পারি তা গণনা করতে হবে। উত্তরটি খুব বড় হলে, ফলাফল মোড 10^9 + 7 ফেরত দিন।
সুতরাং, যদি ইনপুটটি A =[0, 10] এর মত হয়; B =[20, 30], তাহলে আউটপুট 2 হবে, কারণ দুটি সর্বোত্তম সংযোগ রয়েছে, (0 থেকে 20, 10 থেকে 30) এবং (0 থেকে 30, 10 থেকে 20)। উভয় ক্ষেত্রেই, তারের মোট দৈর্ঘ্য 40।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
maxn := 200005 p := 10^9 + 7 Define one array of pair for integer type elements n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: first element of a[i] := A[i] second element of a[i] := 1 for initialize i := n, when i < 2 * n, update (increase i by 1), do: first element of a[i] := B[i - n] second element of a[i] := -1 sort the array a ways := 1, val = 0 for initialize i := 0, when i < 2 * n, update (increase i by 1), do: if val * second element of a[i] < 0, then: ways := ways * |val| val := val + (second element of a[i]) return ways
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B){
long maxn = 200005;
long p = 1000000007;
pair<int, int> a[maxn];
int n = A.size();
for (int i = 0; i < n; i++){
a[i].first = A[i];
a[i].second = 1;
}
for (int i = n; i < 2 * n; i++){
a[i].first = B[i - n];
a[i].second = -1;
}
sort(a, a + 2 * n);
long long ways = 1, val = 0;
for (int i = 0; i < 2 * n; i++){
if (val * a[i].second < 0){
ways = ways * abs(val) % p;
}
val += a[i].second;
}
return ways;
}
int main(){
vector<int> A = { 0, 10 };
vector<int> B = { 20, 30 };
cout << solve(A, B) << endl;
} ইনপুট
{ 0, 10 }, { 20, 30 } আউটপুট
2
