题解 | #Game of Swapping Numbers#

将 $a_i,b_i$ 看作是一段区间，那么考虑每次交换操作的贡献：

可以发现两区间无交集无论如何交换都满足其贡献 $\Delta\ge 0$ （事实上，如果令 $\max\{a_i,b_i\}\le\min\{a_j,b_j\}$ ，那么 $\Delta=2(\min\{a_i,b_i\}-\max\{a_j,b_j\}$ ），而有交集则 $\Delta\le 0$ ，所以一定是尽量地选择有无集的区间交换。

引理： $n>2$ 时，「操作刚好 $k$ 次」和「操作不超过 $k$ 次」是等价的。

证明：将「操作不超过 $k$ 次」的最优解执行完后，因为 $n>2$ ，根据鸽巢原理， $a_i-b_i>0$ 或者 $a_i-b_i<0$ 的情况必然有一个的数量大于等于 $2$ ，那么反复交换这两个区间直到达到 $k$ 次即可。

那么根据引理，将所有 $\max\{a_i,b_i\}$ 和 $\min\{a_j,b_j\}$ 分别从小到大、从大到小 sort 一遍，从前往后扫一遍，当后者大于前者时就将贡献加上，这样做能够使贡献最大化。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
const int N=5e5+10;
int l[N],r[N],x[N],y[N];
int main()
{
    int n=read(),k=read();
    for(int i=1;i<=n;i++)x[i]=read();
    for(int i=1;i<=n;i++)y[i]=read();
    for(int i=1;i<=n;i++)l[i]=min(x[i],y[i]),r[i]=max(x[i],y[i]);
    if(n==2)
    {
        if(k%2)swap(x[1],x[2]);
        printf("%d",abs(x[1]-y[1])+abs(x[2]-y[2]));
    }
    else
    {
        sort(l+1,l+n+1,greater<int>()),sort(r+1,r+n+1);
        ll ans=0;
        for(int i=1;i<=n;i++)ans+=abs(y[i]-x[i]);
        for(int i=1;i<=min(n,k);i++)if(r[i]<l[i])ans+=(l[i]-r[i])*2;
        printf("%lld",ans);
    }
    return 0;
}