โปรแกรม C++ นับวิธีเชื่อมคอมพิวเตอร์กับซ็อกเก็ตให้สายสั้นที่สุด

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A และ B ทั้งคู่มี N องค์ประกอบ พิจารณาว่ามีคอมพิวเตอร์ N เครื่องและซ็อกเก็ต N ตัว พิกัดของคอมพิวเตอร์ตัวที่ i คือ A[i] และซ็อกเก็ตตัวที่ i คือ B[i] พิกัด 2N ตัวนี้ต่างกันทั้งหมด ต้องการเชื่อมคอมพิวเตอร์แต่ละเครื่องกับซ็อกเก็ต 1 ตัว สายแต่ละเส้นเชื่อมได้สูงสุด 1 คอมพิวเตอร์ ต้องการนับจำนวนวิธีที่ทำให้ความยาวสายรวมน้อยที่สุด หากคำตอบใหญ่เกิน ให้คืนค่า mod 10^9 + 7

ตัวอย่าง: A = [0, 10]; B = [20, 30] ผลลัพธ์คือ 2 เพราะมี 2 วิธีที่เหมาะสม: (0-20, 10-30) และ (0-30, 10-20) ทั้งคู่มีความยาวรวม 40

ขั้นตอนการแก้ปัญหา

maxn := 200005
p := 10^9 + 7
กำหนดอาร์เรย์คู่สำหรับเก็บค่า integer
n := ขนาดของ A
สำหรับ i := 0 ถึง n-1:
    a[i].first := A[i]
    a[i].second := 1
สำหรับ i := n ถึง 2n-1:
    a[i].first := B[i-n]
    a[i].second := -1
เรียงลำดับอาร์เรย์ a
ways := 1, val = 0
สำหรับ i := 0 ถึง 2n-1:
    ถ้า val * a[i].second < 0:
        ways := ways * |val| mod p
    val := val + a[i].second
คืนค่า ways

ตัวอย่างโค้ด 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;
}

อินพุต

{ 0, 10 }, { 20, 30 }

เอาต์พุต

2