喜爱福

发布时间 2023-11-28 21:01:44作者: zhujio

Absolute Beauty

将式子$\sum_{i=1}^n |a_i - b_i|$抽象成线段, 手玩一下发现更优情况只出现在相离线段

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

/*
    https://www.luogu.com.cn/problem/CF1898D
    将式子抽象成线段
    $\sum_{i=1}^n |a_i - b_i|$
*/

const int N = 2e5 + 10;

struct node {
    int l, r;
} Seg[N];

int len[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while(T--) {
        int n; cin >> n; int sum = 0;
        for(int i = 1; i <= n; i++) cin >> Seg[i].l;
        for(int i = 1; i <= n; i++) {
            cin >> Seg[i].r; len[i] = abs(Seg[i].l - Seg[i].r); sum += len[i];
            if(Seg[i].r < Seg[i].l) swap(Seg[i].l, Seg[i].r);
        }
        int minr = INT_MAX, maxl = 0;
        for(int i = 1; i <= n; i++) {
            auto [l, r] = Seg[i];
            if(minr > r) {
                minr = r;
                // maxrlen = len[i];
            }
        }
        for(int i = 1; i <= n; i++) {
            auto [l, r] = Seg[i];
            if(maxl < l) {
                maxl = l;
                // maxllen = len[i];
            }
        }
        // cout << maxrlen << ' ' << maxllen << ' ' << maxl << ' ' << minr << endl;
        if(maxl >= minr) cout << sum + 2 * (maxl - minr) << endl;
        else cout << sum << endl;
    }
    return 0;
}
View Code