コンピューターを接続するためのケーブル長を最小化できる方法をいくつカウントするC++プログラム

両方ともN個の要素を持つ2つの配列AとBがあるとします。 N台のコンピューターとN台のソケットがあると考えてください。 i番目のコンピューターの座標はA[i]で、i番目のソケットの座標はb[i]です。これらの2N座標は、ペアごとに異なります。各コンピュータをケーブルでソケットに接続したいと思います。各ソケットは、最大1台のコンピューターに接続できます。ケーブルの長さを最小限に抑える方法をいくつ考えなければなりません。答えが大きすぎる場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がA =[0、10]のような場合。 B =[20、30]の場合、2つの最適な接続（0から20、10から30）と（0から30、10から20）があるため、出力は2になります。どちらの場合も、ケーブルの全長は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