2021牛客暑期多校训练营#1:G-Game of Swapping Numbers

G-Game of Swapping Numbers

原题链接：https://ac.nowcoder.com/acm/contest/11166/G

题目大意

给定两个长度为$n(2\le n\le 5?10^5)$的数组$A,B(?10^8\le A_i,B_i\le 10^8)$,现在对数组$A$操作恰好$k(0\le k\le 10^{18}）$次。

一次操作是选择$A_i,A_j(1\le i<j\le n)$，使之交换。
求最大的$\sum _{i=1}^n\left|A_i?B_i\right|$.

解题思路

进过思考，先判断$n=2$时的情况，由于只有2个，就判断$k$的奇偶性。是偶数，直接输出；反之，交换再输出。

1.当$n>2$时，我们先将$A,B$数组在数轴上表示出来，分类讨论各种交换的状况，发现当某两组数的线段经过交换在数轴上重合的时候，总和会发生改变，这时用数学来表示变化就是$2?(min(A_i,B_i)?max(A_j,B_j))$.
2.然后将最大值和最小值分别排序，前k个进行计算，由于$n\le 3$,所以肯定有符号相同的，符号相同的不论怎么交换都一样，推荐一个小dalao：Spy_Savior，他比我详细，由此可解.

代码实现

#include<bits/stdc++.h>
using namespace std;
long long  n,a[600001],b[600001],c[600001],d[600001],k;
long long ans;
bool cmp(long long  a,long long b){
    return a>b;
}
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],c[i]=max(a[i],b[i]),d[i]=min(a[i],b[i]),ans+=abs(a[i]-b[i]);if(n==2){
    if(!k%2)cout<<ans;else cout<<abs(a[1]-b[2])+abs(a[2]-b[1]);return 0;}sort(d+1,d+n+1,cmp);sort(c+1,c+n+1);for(int i=1;i<=k;i++){
    if(ans+2*(d[i]-c[i])<=ans)break;ans+=2*(d[i]-c[i]);}printf("%lld",ans);
}