Giả sử chúng ta có hai mảng A và B đều có N phần tử. Coi có N máy tính và N ổ cắm. Tọa độ của máy tính thứ i là A [i] và tọa độ của ổ cắm thứ i là b [i]. Các tọa độ 2N này là riêng biệt theo từng cặp. Chúng tôi muốn kết nối mỗi máy tính với một ổ cắm bằng dây cáp. Mỗi ổ cắm có thể được kết nối với nhiều nhất một máy tính. Chúng ta phải đếm xem chúng ta có thể giảm thiểu chiều dài của dây cáp bằng bao nhiêu cách. Nếu câu trả lời quá lớn, hãy trả về kết quả mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là A =[0, 10]; B =[20, 30], thì đầu ra sẽ là 2, vì có hai kết nối tối ưu, (0 đến 20, 10 đến 30) và (0 đến 30, 10 đến 20). Trong cả hai trường hợp, tổng chiều dài của cáp là 40.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
{ 0, 10 }, { 20, 30 } Đầu ra
2