컴퓨터를 연결하기 위해 케이블 길이를 최소화할 수 있는 방법의 수를 세는 C++ 프로그램

N개의 요소가 있는 두 개의 배열 A와 B가 있다고 가정합니다. N 개의 컴퓨터와 N 개의 소켓이 있다고 가정하십시오. i번째 컴퓨터의 좌표는 A[i]이고 i번째 소켓의 좌표는 b[i]입니다. 이러한 2N 좌표는 쌍으로 구별됩니다. 우리는 케이블로 소켓으로 각 컴퓨터를 연결하고 싶습니다. 각 소켓은 최대 한 대의 컴퓨터에 연결할 수 있습니다. 우리는 케이블 길이를 최소화할 수 있는 방법이 얼마나 많은지 계산해야 합니다. 답이 너무 크면 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 A =[0, 10]과 같으면; B =[20, 30], 두 개의 최적 연결(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