CF1651C 超好理解的题解

Fall_X · 2022-03-15 21:38:46 · 题解

首先考虑怎样连接合法。

如果没有线连接两排编号为 1 或 n 的电脑上，那么断掉连接处就会使网络分裂，换而言之，每排编号 1、n 的电脑一定会有线连接，也只需要连接这些线段。

对于每一排编号为 1、n 的电脑，循环遍历对面的电脑，找到花费最小的一个连接，但此处也需要特判 1 和 1、n 和 n、1 和 n 相互连接的情况。

#include <bits/stdc++.h>
using namespace std;
long long t, n, a[200010], b[200010], ans, ta1, tam, tb1, tbn;
int main() {
    ios::sync_with_stdio(0);
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++) cin >> b[i];
        ta1 = tam = tb1 = tbn = 4e18;
        for(int i = 1; i <= n; i++) ta1 = min(ta1, abs(a[1] - b[i]));
        for(int i = 1; i <= n; i++) tam = min(tam, abs(a[n] - b[i]));
        for(int i = 1; i <= n; i++) tb1 = min(tb1, abs(a[i] - b[1]));
        for(int i = 1; i <= n; i++) tbn = min(tbn, abs(a[i] - b[n]));
        ans = min(abs(a[1] - b[1]) + abs(a[n] - b[n]), abs(a[1] - b[n]) + abs(a[n] - b[1]));
        ans = min(ans, min(abs(a[1] - b[1]) + tam + tbn, abs(a[n] - b[n]) + ta1 + tb1));
        ans = min(ans, min(abs(a[1] - b[n]) + tam + tb1, abs(a[n] - b[1]) + ta1 + tbn));
        ans = min(ans, ta1 + tb1 + tam + tbn);
        cout << ans << endl;
    }
    return 0;
}