G-Game of Swapping Numbers

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\}\),在数轴上画出G-Game of Swapping Numbers
??如果想要使得获取到的值变大,我们就要想什么样的区间是对我们有益的。从上图我们可以看出,对于\((6,8),(9,10)\)两个没有交集的区间,无论我们如何交换两个区间的端点,区间的间隔都将会加入结果中,也就是我们可以获取更大的值。而对于区间\((2,7),(6,8)\)而言,一旦交换\(6,7\)就会导致我们的区间长度变小,因此从获取最大值的角度上,我们交换选择的端点,其贡献为\(2*(min(a_i,b_i)-max(a_j,b_j))\),如果小于\(0\),说明存在交集,不需要交换。G-Game of Swapping Numbers
??由于题目存在交换次数的限制,所以我们还需要考虑次数的影响。由于当\(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;
}

G-Game of Swapping Numbers

上一篇:[Axure RP 9]怎么让鼠标移动到某元件上变成小手


下一篇:linux 执行 shell 文件报错 /usr/bin/env: "bash\r"