2021牛客多校1

G-Game of Swapping Numbers（思维）

题意：

给定一个两个数组 $A[],B[]$ ，定义一种操作：$swap(A[i],A[j])|(1\le i<j\le n)$ 。现要求对一个数组 $A$ 进行 $K$ 次操作，使得 ${\sum }_{i=1}^n|A_i-B_j|$ 最大。

思路：

将 $[A_i,B_i]$ 与 $[A_j,B_j]$ 看成两个区间，再数轴上画出来，再交换 $A_i,A_j$。

可以发现，如果两个区间相交，则交换后，贡献不变（这个可以用于多次无效交换）；

若区间不相交，那么交换后，贡献增加 $2\ast max(A_i,A_j)-min(B_i,B_j)|(A_i<B_i\&A_j<B_j)$

多画几个，可以发现，其实不管 $A_i$ 与 $B_i$ 的大小如何，增加的贡献总是两个区间之间的距离 $\ast 2$。

所以可以将 $A_i=max(A_i,B_i),B_i=max(A_i,B_i)$

考虑贪心，每次取区间间距最大的两个区间进行交换，直到没有不相交的区间，剩余操作次数直接在相交区间上进行无效操作来补充。

注意特判，当 $n=2$ 时，要特判，因为要此时没有无效操作可以来补充交换次数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &b[i]);
        ans += abs(a[i] - b[i]);
    }

    vector<ll> aa(n), bb(n);
    for (int i = 0; i < n; i++) {
        aa[i] = min(a[i], b[i]);
        bb[i] = max(a[i], b[i]);
    }

    sort(aa.begin(), aa.end(), less<ll>());
    sort(bb.begin(), bb.end());

    for (int i = 0; i < min(n, k); i++) {
        if (aa[i] >= bb[i]) {
            ans += 2LL * (aa[i] - bb[i]);
        }
        else break;
    }
    printf("%lld\n", ans);

    return 0;
}

/*
3 2
1 2 3
3 2 1
*/

K-Knowledge Test about Match（贪心）

题意：

给定 $a=\{0,1,2,3,\dots ,n-1\},b=\{b_0,b_1,\dots ,b_{n-1}\}$。 你可以对 $b$ 数组进行重排操作

使得 ${\sum }_{i=0}^{n-1}\sqrt{|a_i-b_i|}$ 最小。误差可以在 $4\%$ 以内。

思路：

因为 $\sqrt{x}$ 的函数图像在 $x$ 很大时，增长得非常慢，而在 $x$ 较小的时候，增长幅度非常大。

所以考虑贪心，先匹配差值为 $0$ 的对，在匹配差值为 $1$ 的对，$\dots$ 最后匹配差值为 $n-1$ 的对 。

还有一个奇怪的做法：

每次枚举所有点对，计算交换的后的贡献是增加还是减少，若减少，就交换。（$O(n^2)$）做 $15$ 次。

虽然不懂，但我大受震撼

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> b(n), vis(n), ans(n, -1);
        for (int i = 0; i < n; i++) {
            scanf("%d", &b[i]);
            vis[b[i]]++;
        }
 
        for (int s = 0; s < n; s++) {
            for (int i = 0; i < n; i++) {
                if (vis[i] > 0 && i - s >= 0 && ans[i - s] == -1) {
                    ans[i - s] = i;
                    vis[i]--;
                }
                if (vis[i] > 0 && i + s < n && ans[i + s] == -1) {
                    ans[i + s] = i;
                    vis[i]--;
                }
            }
        }
 
        for (int i = 0; i < n; i++)
            printf("%d ", ans[i]);
        printf("\n");
    }
 
    return 0;
}
 
 
/*
2
10
4 8 9 9 6 1 3 9 5 2
54
0 0 0 1 2 2 4 4 5 6 7 10 16 17 18 19 19 20 23 24 25 26 26 26 27 29 30 30 31 32
32 33 34 36 37 37 38 39 41 42 42 43 43 44 44 45 45 46 50 50 51 53 53 53
*/