【牛客竞赛】Game of Swapping Numbers题解

ACM-ICPC

Publish Date: 2021-07-28

题目大意

给出有 $n$ 个数的数组 $a$，$b$，以及自然数 $k$，你必须恰好交换 $a$ 中任意两个数 $k$ 次，且在此基础上，使 $\sum |a_i - b_i|$ 最大。

思路

我们可以先考虑考虑什么情况下，交换两个数会使结果更优。

我们可以在纸上画一个数轴，在这里我就用字符表示了。

对于下面这种情况

——-a1———-b1———-a2———b2———>

$|a_1 - b_1|$ 与 $|a_2 - b_2|$ 可以看作 $a_1$ 与 $b_1$，以及 $a_2$ 与 $b_2$ 的距离，

不难发现，如果此时交换 $b_1, a_2$，那么就会变为

——-a1———-a2———-b1———b2———>

那么 $|a_1 - b_1| + |a_2 - b_2|$ 显然就会变大。

而这个变大的值，就是 $2 \cdot |a_2 - b_1|$。

进一步我们发现，如果原本的情况是

——-b1———-a1———-b2———a2———> (间距与最开始情况一样，只是顺序变了)

那么其实交换后，增大的值是一样的。

其实就是 $a_1, b_1$ 与 $a_2, b_2$ 最接近的部分的两倍，用数学语言表示，就是:
$2 \cdot (\min(a_2, b_2) - \max(a_1, b_1))$
而一旦 $\min(a_2, b_2) \le \max(a_1, b_1)$，那么交换不会使结果更优，甚至在 $\min(a_2, b_2) < \max(a_1, b_1)$ 的情况下交换还会使结果更差。
那么我们就需要知道怎么利用这 $k$ 次交换。我们先来考虑一下最优的情况是什么。

我们考虑 $n > 2$ 的情况：

首先，最优的情况一定是 $a$，$b$ 数组中，按照从大到小排序，用前面一半的数，减去后面一半的数。

比如如下数组:

a: 2 4 8

b: 3 7 1

那么结果显然为 $8 + 7 + 4 - 3 - 2 - 1$，它可由以下结果得出：

$|8 - 3| + |7 - 3| + |4 - 1|$ 得到

也可由 $|8 - 2| + |7 - 1| + |4 - 2|$ 得到

假如我们已经得到了最优的情况，我们可以任意地交换在后一半的数，结果还是不会变的。（因为绝对值符号内的数正负没有改变，所以绝对值的和也不会改变），所以我们就能得出结论:

$n > 2$ 时，只要我们已经得到了最优解，那么无论再操作多少次，我们都能得到最优解。

而 $n = 2$ 时，因为无法保证可以交换在排序中属于后半部分的，所以得到了最优解，那么如果再交换一次，就只能得到非最优解。

比如:

a: 1 8

b: 2 6

最优解显然为 $|8 - 2| + |6 - 1|$，但是再交换时，在排序中为后半部分的1,2却无法交换，所以只能交换1,8，从而结果就会变小。

（而 $n > 2$ 时，那么肯定可以找到两个属于前半部分，或者同时属于后半部分的两个数）
那么我们具体做的时候，若 $n > 2$，只需计算 $\min(a_i, b_i)$ 和 $\max(a_i, b_i)$ 数组，然后从 $\min$ 数组中最大的开始，去从小到大减 $\max$ 数组中的数（这样可以保证在 $k$ 不够用的时候尽量扩大结果），就可以了。$n = 2$ 时，单独判断即可。

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxN = 5e5 + 5;

int n, k, a[maxN], b[maxN], l[maxN], r[maxN];
long long ans;

bool cmp1(int x, int y)
{
    return x < y;
}

bool cmp2(int x, int y)
{
    return x > y;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        l[i] = min(a[i], b[i]);
        r[i] = max(a[i], b[i]);
    }
    if(n == 2) {
        if(k % 2)
            swap(a[1], a[2]);
        printf("%d", abs(a[1] - b[1]) + abs(a[2] - b[2]));
        return 0;
    }
    sort(l + 1, l + 1 + n, cmp2);
    sort(r + 1, r + 1 + n, cmp1);
    for(int i = 1; i <= n; ++i)
        ans += abs(a[i] - b[i]);
    for(int i = 1; i <= min(n, k); i++) {
        if (r[i] < l[i]) {
            ans += (l[i] - r[i]) << 1;
        }
    }
    printf("%lld\n", ans);
    return 0;
}