数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告