मान लीजिए हमारे पास N-तत्वों वाले दो ऐरे A और B हैं। मान लें N कंप्यूटर और N सॉकेट हैं। iवें कंप्यूटर का निर्देशांक A[i] है और iवें सॉकेट का निर्देशांक 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 पूर्णांक प्रकार के तत्वों के लिए जोड़ी का एक ऐरे परिभाषित करें n := A का आकार i := 0 से n-1 तक, करें: a[i] का पहला तत्व := A[i] a[i] का दूसरा तत्व := 1 i := n से 2*n-1 तक, करें: a[i] का पहला तत्व := B[i - n] a[i] का दूसरा तत्व := -1 ऐरे a को सॉर्ट करें ways := 1, val = 0 i := 0 से 2*n-1 तक, करें: यदि val * a[i] का दूसरा तत्व < 0, तो: ways := ways * |val| val := val + a[i] का दूसरा तत्व 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