Game of Swapping Numbers

题目大意

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

思路

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

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

   对于下面这种情况

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

   $|a_1 - b_1|$与可以看作 $a_1$ 与$ b_1$​​的距离 ，

   不难发现，如果此时交换b1，a2，那么就会变为

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

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

   而这个变大的值，就是$2 * |a2 - b1|$

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

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

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

   其实就是 a1，b1 与 a2,b2最接近的部分的两倍，用数学语言表示，就是:

   $2* (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))$情况下交换还会使结果更差。​

2. 那么我们就需要知道怎么利用这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$​ 时，那么肯定可以找到两个属于前半部分，或者同时属于后半部分的两个数）

3. 那么我们具体做的时候，若$ n > 2$,则只需计算$min(a_i, a_j), max(b_i, b_j)$​​​数组，然后从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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/07/28/Game-of-Swapping-Numbers/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！