CF1921D题解

Eternity_Yoke · 2024-01-18 14:33:27 · 题解

题目大意

给定两个数组，a 数组长度为 n，b 数组长度为 m，m\ge n。

在 b 数组中随意选取 n 个元素组成长度为 n 新数组 c。

要求 D={\textstyle \sum_{i = 1}^{n}}\left | a_i - c_i \right | 的值最大。

解题思路

容易想到用 a 数组的最小值与 b 数组的最大值进行匹配。

但到了中间某处会存在更优解，即此时 a_i 与 b 数组的最小值匹配更优。

考虑进行两次遍历。

第一次用 a 数组的最小值与 b 数组的最大值依次匹配。

第二次用 a 数组的最大值与 b 数组的最小值依次匹配。

最终两次中 i 位置 D_i 值更大的对答案进行贡献。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int t,n,m,x,y;
ll D;
int a[N],b[N],f1[N],f2[N];
int main()
{   ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {   cin>>n>>m;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        for(int i=1;i<=m;i++)
        cin>>b[i];
        sort(a+1,a+n+1);
        sort(b+1,b+m+1);
        for(int i=1;i<=n;i++)
        {   f1[i]=abs(a[i]-b[m-i+1]);
            f2[i]=abs(a[i]-b[n-i+1]);
        }
        D=0;
        for(int i=1;i<=n;i++)
        D+=max(f1[i],f2[i]);
        cout<<D<<endl;
    }
    return 0;
}