题解：CF1651C Fault-tolerant Network

zhangmuning1016 · 2025-03-21 16:52:21 · 题解

题意

起初，对于每一排电脑，所有相邻的电脑之间有网线连接。因此两排电脑是相互独立的两套计算机网络。将第一排的第 i 台电脑和第二排的第 j 台电脑相连需要花费 \lvert a_i - b_j \rvert ，你需要保证的是，不管哪台电脑坏掉，这个网络的剩余部分都不会断开。

思路

这道题很明显是一道贪心，我们发现 (1,1)，(1,n)，(2,1)，(2,n) 要与另一排连接。这样可以保证计算机坏了后网络还是连通的。

• 四根线与另一排连接。

三种情况都扫描一遍求最小值即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200010],b[200010];
signed main() {
    int T;
    cin>>T;
    while(T--) {
        int n;
        int ans;
        cin>>n;
        for(int i=1; i<=n; i++)cin>>a[i];
        for(int i=1; i<=n; i++)cin>>b[i];
        ans=abs(a[1]-b[1])+abs(a[n]-b[n]);
        ans=min(ans,abs(a[n]-b[1])+abs(a[1]-b[n]));
        int a1,an,b1,bn;
        a1=b1=an=bn=0x3f3f3f3f;
        for(int i=1; i<=n; i++) {
            a1=min(a1,abs(a[1]-b[i]));
            an=min(an,abs(a[n]-b[i]));
            b1=min(b1,abs(b[1]-a[i]));
            bn=min(bn,abs(b[n]-a[i]));
        }
        ans=min(ans,abs(a[1]-b[1])+bn+an);
        ans=min(ans,abs(a[1]-b[n])+an+b1);
        ans=min(ans,abs(b[1]-a[n])+bn+a1);
        ans=min(ans,abs(b[n]-a[n])+b1+a1);
        ans=min(ans,a1+an+b1+bn);
        cout<<ans<<endl;
    }
    return 0;
}