Cho hai mảng A và B kích thước N. N máy tính tại tọa độ A[i], N ổ cắm tại B[i]. 2N tọa độ phân biệt. Nối mỗi máy với một ổ cắm (mỗi ổ cắm tối đa một máy). Đếm số cách nối sao cho tổng độ dài cáp tối thiểu. Kết quả modulo 10^9+7.
Ví dụ
Với A = [0, 10]; B = [20, 30], đầu ra 2. Hai cách tối ưu: (0-20, 10-30) và (0-30, 10-20), tổng độ dài đều 40.
Giải thuật
Gộp hai mảng thành một mảng cặp (tọa độ, loại) với loại = 1 (máy) hoặc -1 (ổ cắm). Sắp xếp theo tọa độ. Duyệt, giữ biến val là chênh lệch số máy và ổ cắm đã thấy. Khi val * loại < 0 (gặp loại đối lập khi đang có dư), nhân số cách với |val|. Cập nhật val += loại.
Mã 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;
}
Đầu vào / Đầu ra
Input: { 0, 10 }, { 20, 30 }
Output: 2