题目
题意：给定两排网络 a a a和 b b b，每排电脑数为 n ( 3 < = n < = 1 0 5 ) n(3<=n<=10^5) n(3<=n<=105)，同排的网络，相邻电脑网线是相通的，现要将这两排网络连通。要求：当出现一台电脑故障时，网络仍是相同的。即一台电脑故障，不会把电脑拆分为多个网络。两台电脑相连的代价为 ∣ a i ? b j ∣ |a_i-b_j| ∣ai??bj?∣，要求输出最小代价。
【Codeforces|Fault-tolerant Network（连通块/贪心）】参考
思路：
1、边上的网络一定要通， a 1 , a n , b 1 , b n a_1,a_n,b_1,b_n a1?,an?,b1?,bn?，假设 a 1 a_1 a1?不通，由于 a 1 a_1 a1?只和 a 2 a_2 a2?相连，那么当 a 2 a_2 a2?故障后， a 1 a_1 a1?就和其他网络失联了。
2、在1的前提下，非边上的网络可以不通。假设 a i a_i ai?挂了，该排被拆分为 a 1 , . . , a i ? 1 a_1,..,a_{i-1} a1?,..,ai?1?和 a i + 1 , . . . , a n a_{i+1},...,a_n ai+1?,...,an?，由于 a 1 , a n a_1,a_n a1?,an?和 b b b相通，整个网络还是通的。
怎么求 a 1 , a n , b 1 , b n a_1,a_n,b_1,b_n a1?,an?,b1?,bn?相通的最小代价？对于 a 1 a_1 a1?来说，它可以连接 b 1 , b n b_1,b_n b1?,bn?以及最小代价 b m n 1 b_{mn1} bmn1?；对于 a n a_n an?同理，它可以连接 b 1 , b n b_1,b_n b1?,bn?以及最小代价 b m n 2 b_{mn2} bmn2?。我们枚举 a 1 , a n a_1,a_n a1?,an?的连接情况，求出对应的代价，取最小值。
官方代码
#includeusing namespace std;
#define fore(i, l, r) for(int i = int(l);
i < int(r);
i++)typedef long long li;
const int INF = int(1e9);
int n;
vector a, b;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
b.resize(n);
fore (i, 0, n)
cin >> b[i];
return true;
}int bestCandidate(const vector &vals, int cur) {
int bst = INF + 10, pos = -1;
fore (i, 0, n) {
if (bst > abs(cur - vals[i])) {
bst = abs(cur - vals[i]);
pos = i;
}
}
return pos;
}inline void solve() {
li bst = 10ll * INF;
vector cds1 = {0, bestCandidate(b, a[0]), n - 1};
vector cds2 = {0, bestCandidate(b, a[n - 1]), n - 1};
for (int var1 : cds1) {
for (int var2 : cds2) {
li ans = (li)abs(a[0] - b[var1]) + abs(a[n - 1] - b[var2]);
if (var1 > 0 && var2 > 0)// b[0]不通，需要连通b[0]
ans += abs(b[0] - a[bestCandidate(a, b[0])]);
if (var1 < n - 1 && var2 < n - 1)// b[n-1]不通，需要连通b[n-1]
ans += abs(b[n - 1] - a[bestCandidate(a, b[n - 1])]);
bst = min(bst, ans);
}
}
cout << bst << endl;
}int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
read();
solve();
}
return 0;
}
推荐阅读
- 算法|K-means，K-means++方法详解-机器学习分类问题常见算法
- 算法|PyTorch中的squeeze()和unsqueeze()详解与应用案例
- 机器学习|bagging && boosting && stacking 集成学习
- 算法|Fractal解题笔记
- 动态规划|符环 解题笔记
- leetcode刷题记录|移动零——LeetCode283题
- leetcode刷题记录|反转字符串——LC344题
- leetcode刷题记录|两数之和II - 输入有序数组——LC167题（中等难度）
- 最小生成树-克鲁斯卡尔算法(Kruskal算法)