মান লিখুন: আমাদের কাছে N উপাদান বিশিষ্ট দুটি অ্যারে A এবং B রয়েছে। Nটি কম্পিউটার এবং Nটি সকেট আছে। i-তম কম্পিউটারের কোঅর্ডিনেট A[i] এবং i-তম সকেটের কোঅর্ডিনেট B[i]। এই 2Nটি কোঅর্ডিনেট পার-ওয়াইজ আলাদা। প্রতিটি কম্পিউটারকে একটি সকেটের সাথে ক্যাবল দিয়ে সংযুক্ত করতে হবে। প্রতিটি সকেটেสูงোচ্চ একটি কম্পিউটার সংযুক্ত করা যাবে। ক্যাবলের মোট দৈর্ঘ্য ন্যূনতম করার কতগুলো উপায় আছে তা বের করতে হবে। উত্তর বড় হলে 10⁹+7 দিয়ে মডুলো নিন।
উদাহরণ
যদি ইনপুট হয় A = [0, 10]; B = [20, 30], তবে আউটপুট হবে 2, কারণ দুটি অপ্টিমাল সংযোগ আছে: (0-20, 10-30) এবং (0-30, 10-20)। দুটি কেসে মোট দৈর্ঘ্য ৪০।
সমাধানের ধাপসমূহ
maxn := 200005
p := 10⁹ + 7
পেয়ার অ্যারে a তৈরি করুন
n := A এর আকার
for i := 0 থেকে n-1:
a[i].first := A[i], a[i].second := 1
for i := n থেকে 2n-1:
a[i].first := B[i-n], a[i].second := -1
a সর্ট করুন
ways := 1, val := 0
for i := 0 থেকে 2n-1:
যদি val * a[i].second < 0:
ways := ways * |val| mod p
val := val + a[i].second
ways রিটার্ন করুন
C++ বাস্তবায়ন
#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
