CodeForces - 1921D Very Different Array

引理：
对于等长的长度为$n$的$a,b$序列，让$a,b$以相反的顺序排序使得${\sum }_{i=1}^n|a[i]-b[i]|$为最大值

那么对于不能等长的序列，长度为$n,m$的序列$a,b$，其中$n<=m$。我们可以理解成，每次从$a$里挑选一个数字，在$b$里找一个最大的值匹配。

首先将$a,b$按非递减排序，$ai,aj,bi,bj$分别对应着当前两个序列的最小值和最大值。
那么最大收益为$max(abs(a[ai]-b[bj]),abs(a[aj]-b[bi]))$

对于$a[ai]$他的可以选择的对象有两个，分别是$b[ai],b[bj]$，但是$a[ai]$一定不能选择$b[ai]$，假设他选择$b[ai]$可以让当前情况最大化，那么$b[ai]$一定小于$a[ai]$，换句话说$a[aj]$一定能得到更大的收益。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{int n, m;cin >> n >> m;vector<int> a(n + 1), b(m + 1);for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= m; i++){cin >> b[i];}sort(a.begin() + 1, a.begin() + 1 + n);sort(b.begin() + 1, b.begin() + 1 + m);int ai = 1, aj = n, bi = 1, bj = m;ll res = 0;while (ai <= aj){int f1 = abs(a[ai] - b[bj]), f2 = abs(a[aj] - b[bi]);if (f1 >= f2){ai++;bj--;}else{aj--;bi++;}res += max(f1, f2);}cout << res << "\n";
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){solve();}
}