สมมติว่าเรามีอาร์เรย์ A และ B สองอาร์เรย์ที่มีองค์ประกอบ N พิจารณาว่ามีคอมพิวเตอร์ N และซ็อกเก็ต N พิกัดของคอมพิวเตอร์ ith คือ A[i] และพิกัดของซ็อกเก็ต ith คือ b[i] พิกัด 2N เหล่านี้มีความแตกต่างกันเป็นคู่ เราต้องการเชื่อมต่อคอมพิวเตอร์แต่ละเครื่องกับซ็อกเก็ตด้วยสายเคเบิล แต่ละซ็อกเก็ตสามารถเชื่อมต่อกับคอมพิวเตอร์ได้ไม่เกินหนึ่งเครื่อง เราต้องนับว่าเราสามารถลดความยาวของสายเคเบิลได้หลายวิธี หากคำตอบมีขนาดใหญ่เกินไป ให้คืนค่า mod ผลลัพธ์ 10^9 + 7
ดังนั้น หากอินพุตเป็น A =[0, 10]; B =[20, 30] ดังนั้นเอาต์พุตจะเป็น 2 เนื่องจากมีการเชื่อมต่อที่เหมาะสมที่สุดสองแบบ (0 ถึง 20, 10 ถึง 30) และ (0 ถึง 30, 10 ถึง 20) ในทั้งสองกรณี ความยาวรวมของสายเคเบิลคือ 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
