資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式計算連線計算機以最小化電纜長度的方法數
假設我們有兩個陣列 A 和 B，都包含 N 個元素。假設有 N 臺計算機和 N 個插座。第 i 臺計算機的座標是 A[i]，第 i 個插座的座標是 b[i]。這 2N 個座標是成對不同的。我們想用電纜將每臺計算機連線到一個插座。每個插座最多隻能連線一臺計算機。我們必須計算以多少種方式可以最小化電纜的長度。如果答案太大，則返回結果模 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
更新於: 2022年3月3日
236 次檢視
廣告