DDOSvoid's Blog

2021牛客多校1 G Game of Swapping Numbers

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

https://ac.nowcoder.com/acm/contest/11166/G

Solution

  1. 首先我们思考如何求可以交换无限次后这个东西的最大值

    我们首先考虑将绝对值拆开，那么相当于在 $a_i$ 和 $b_i$ 上分别加上正号和负号，且只需要总的正号的数量等于负号的数量即可，不要求 $a$ 中的正号等于负号的数量，那么这个时候最大值就是将 $a$ 和 $b$ 中的所有数拿出来排序然后前 $n$ 个取正号，后 $n$ 个取负号

    另外我们需要知道，有可能出现正负号和实际绝对值相反的情况，但是如果交换这一对正负号，只会使得解变优，所以在题目求最优的前提下，正负号是可以随意分配的

  2. 接下来我们考虑给定 $a$ 和 $b$ 后如何求最小需要交换多少次可以达到最大值

    我们按照之前的想法将符号分配好，那么需要交换的都是 $(+a_i,+b_i)$ 和 $(-a_i,-b_i)$，所以我们每次换一下 $++$ 和 $—$ 即可，注意到 $++$ 的数量一定等于 $—$ 的数量

  3. 然后我们在思考给定 $a$ 和 $b$ 以及可以交换的次数 $k$ 之后，如何求恰好交换 $k$ 次后的最大值

    首先给出一个结论，在 $n>2$ 的情况下，恰好交换 $k$ 次和至多交换 $k$ 次是一样的

    不妨假设我们交换了 $s(s<k)$ 次就得到了最优答案且已经分配好了符号，那么 $a$ 中至少有两个 $a$ 是同符号的，我们只需要交换这两个 $a$ 即可

    那么在有这个结论之后，我们考虑如何交换，对于 $(a_i,b_i)$ 和 $(a_j,b_j)$，如果交换之后答案更优，需要这两个区间没有交点，且交换之后的价值会增加 $2\times (min\lbrace a_i,b_i\rbrace-max\lbrace a_j,b_j\rbrace)$，通过这个式子我们发现可以将贡献拆开，那么我们直接对于 $min\lbrace a_i,b_i\rbrace $ 和 $-max\lbrace a_i,b_i\rbrace$ 排序取前 $k$ 大相加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#define maxn 500010
#define ll long long
using namespace std;

int n, k, a[maxn], b[maxn];

int A[maxn], B[maxn];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k; ll ans = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    if (n == 2) {
        if (k & 1) swap(a[1], a[2]);
        cout << abs(a[1] - b[1]) + abs(a[2] - b[2]);
        return 0; 
    }
    for (int i = 1; i <= n; ++i) ans += abs(a[i] - b[i]);
    for (int i = 1; i <= n; ++i) A[i] = -max(a[i], b[i]), B[i] = min(a[i], b[i]);
    sort(A + 1, A + n + 1, greater<int>());
    sort(B + 1, B + n + 1, greater<int>());
    for (int i = 1; i <= min(n, k) && A[i] + B[i] > 0; ++i)
        ans += 2 * (A[i] + B[i]); 
    cout << ans << "\n"; 
}