【牛客竞赛】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;
}

祝大家看的开心 （意味深）