题解：CF1651C Fault-tolerant Network

题意

起初，对于每一排电脑，所有相邻的电脑之间有网线连接。因此两排电脑是相互独立的两套计算机网络。将第一排的第

i

台电脑和第二排的第

j

台电脑相连需要花费

\lvert a_i - b_j \rvert

，你需要保证的是，不管哪台电脑坏掉，这个网络的剩余部分都不会断开。

思路

这道题很明显是一道贪心，我们发现

(1,1)

，

(1,n)

，

(2,1)

，

(2,n)

要与另一排连接。这样可以保证计算机坏了后网络还是连通的。

$(1,1)$ ， $(1,n)$ 与 $(2,1)$ ， $(2,n)$ 两两相连。
$(1,1)$ ， $(1,n)$ 其中一个与 $(2,1)$ ， $(2,n)$ 其中一个连接。
四根线与另一排连接。

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

代码

CPP

#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;
}

题解：CF1651C Fault-tolerant Network

文章操作

题意

思路

代码

相关推荐

评论

题解：CF1651C Fault-tolerant Network