526互联

Codeforces Round 910 (Div. 2) D. Absolute Beauty（数论）

发布时间 2023-12-16 21:40:50作者: ikunhuaji
Codeforces Round 910 (Div. 2) D. Absolute Beauty

思路：

将每个 \(a_i\) 与 \(b_i\) 转化为线段，大数在后，小数在前

即 L ( min) —— R (max)

对于 \(b_i\) 和 \(b_j\) 的 交换 ：

  1. ​ L1 —— R1 L2 —— R2

若 两线段原本不相交，则会使两线段相交，长度和 +=\(2*( L2 - R1 )\)

  1. 若原本相交，则会使线段分开，负贡献或者无贡献

因此要尽可能选用两条相隔最远的不相交线段

我们可以记录 最小的右端点 R ,找到最大的左端点 L

答案为 原所有线段和 sum + \(2*( MaxL2 - MINR1 )\)

#define int long long
#define LL long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define ppb pop_back()
#define pb push_back
#define pf push_front
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ikun ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
//mp.reserve(1024);
//mp.max_load_factor(0.25);

//auto check = [&]()->bool
//    {
//
//    };

using namespace std;

const int N = 2e5 + 10;

int a[N], b[N];


signed main()
{
    ikun;

    int t;
    t = 1;
    cin >> t;

    auto solve = [&]()->void
        {
            int n;
            cin >> n;

            for (int i = 1; i <= n; i++)
            {
                cin >> a[i];
            }
            for (int i = 1; i <= n; i++)
            {
                cin >> b[i];
            }

            vector<pair<int, int>>s(n + 5);

            int sum = 0;

            for (int i = 1; i <= n; i++)
            {
                s[i] = minmax(a[i], b[i]);
                sum += abs(a[i] - b[i]);
            }

            int mx = 0;
            int r = (int)1e9;

            sort(s.begin() + 1, s.begin() + 1 + n);

            for (int i=1;i<=n;i++)
            {
                mx = max(mx, s[i].first - r);
                r = min(r, s[i].second);
            }

            cout << sum + 2*mx << endl;
        };

    while (t--)
    {
        solve();
    }

    return 0;
}