मान लीजिए कि हमारे पास एन तत्वों के साथ दो एरे ए और बी हैं। विचार करें कि एन कंप्यूटर और एन सॉकेट हैं। ith कंप्यूटर का निर्देशांक A[i] है और ith सॉकेट का निर्देशांक b[i] है। ये 2N निर्देशांक युग्म-वार भिन्न हैं। हम प्रत्येक कंप्यूटर को केबल द्वारा सॉकेट से जोड़ना चाहते हैं। प्रत्येक सॉकेट को अधिकतम एक कंप्यूटर से जोड़ा जा सकता है। हमें यह गिनना होगा कि हम केबलों की लंबाई को कितने तरीकों से कम कर सकते हैं। अगर उत्तर बहुत बड़ा है, तो परिणाम मोड 10^9 + 7 लौटाएं।
इसलिए, यदि इनपुट ए =[0, 10] जैसा है; बी =[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