Game of Swapping Numbers
题意
给定两个长度为\(n\)的数组\(a、b\)，计算\(\sum_{i=1}^n\mid a_i-b_i\mid\)。现要对\(a\)数组中任意两个元素交换位置，经过\(k\)次操作，输出能够获取到的最大值。
思路
假设给定数组\(a=\left\{2,8,9\right\}\),\(b=\left\{7,6,10\right\}\)，在数轴上画出
如果想要使得获取到的值变大，我们就要想什么样的区间是对我们有益的。从上图我们可以看出，对于\((6,8),(9,10)\)两个没有交集的区间，无论我们如何交换两个区间的端点，区间的间隔都将会加入结果中，也就是我们可以获取更大的值。而对于区间\((2,7),(6,8)\)而言，一旦交换\(6,7\)就会导致我们的区间长度变小，因此从获取最大值的角度上，我们交换选择的端点，其贡献为\(2*(min(a_i,b_i)-max(a_j,b_j))\)，如果小于\(0\)，说明存在交集，不需要交换。
由于题目存在交换次数的限制，所以我们还需要考虑次数的影响。由于当\(n>2\)时，根据抽屉原理，\(a_i>b_i\)或者\(a_i<b_i\)中的一种情况必然出现两次，因此对于至多\(k\)次操作是等价于必须\(k\)次操作的，因为我们只需要不断交换两个同一情况的区间，直到交换次数达到\(k\)次。而当\(n==2\)时，我们只需要对\(k\)的奇偶性进行判断是否需要交换即可。
因此，我们只需要用两个数据分别存储\(min(a_i,b_i),max(a_i,b_i)\),再分别按照从大到小、从小到大的顺序排好，依次取前\(min(n,k)\)个数计算贡献即可(这样每次贡献的区间长度是最大的)。
参考代码
点此展开
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;
const int N=5e5+10;
ll n,k;
ll a[N],b[N];
ll u[N],d[N];//u[i]存储较小值，d[i]存储较大值
bool cmp(const ll &l,const ll &r)
{
return l>r;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
ll res=0;//注意结果可能很大
for(int i=1;i<=n;i++)
{
res+=abs(a[i]-b[i]);
u[i]=min(a[i],b[i]);
d[i]=max(a[i],b[i]);
}
if(n==2)
{
if(k&1)
swap(a[1],a[2]);
res=abs(a[1]-b[1])+abs(a[2]-b[2]);
cout<<res<<endl;
return 0;
}
sort(u+1,u+n+1,cmp);
sort(d+1,d+n+1);
for(int i=1;i<=min(n,k);i++)
{
if(u[i]>d[i])
res+=2*(u[i]-d[i]);
else
break;
}
cout<<res<<endl;
return 0;
}