2021牛客暑期多校训练营（第一场）G

题目描述

Given two arrays $A$ , $B$ with length $N$ , you should perform exactly $K$ operations in array $A$ .

For each operation, choose $2$ elements $A_i$ , $A_j$ ( $1≤i<j≤N$ ) and swap the positions of $A_i$ and $A_j$ .

Please maximize $\sum\limits_{i = 1}^{n}|A_i-B_i|$ .

输入描述

The first line of input contains two integers $N,K$ ( $2≤N≤5×10^5$ , $0≤K≤10^8$ ), describing the length of $A$ , $B$ and number of operations.

The second line contains $N$ integers $A_1,...,A_N$ ( $−10^8≤A_i≤10^8$ ).

The third line contains $N$ integers $B_1,...,B_N$ ( $−10^8≤B_i≤10^8$ ).

输出描述

Output one integer, the maximum answer.

示例1

输入

3 2
1 2 3
3 2 1

输出

示例2

输入

3 2
1 2 3
1 2 3

输出

示例3

输入

3 1
1 2 3
3 2 1

输出

思路

考虑任意一个最优解，我们把交换后的数字重新放回原来的位置，相当于为每个元素分配了在最优解中的符号再相加。只需要满足 $A$ 中正号与 $B$ 中负号相等、 $A$ 中负号与 $B$ 中正号即可，进而可以得到只需要 $A,B$ 中正负号的总和各为 $N$ 即可。假设我们能任意指定 $k$ 来求最优解，相当于是把 $A, B$ 合在一起排序，取最大的 $N$ 个填正号，最小的 $N$ 个填负号即可。

首先考虑如何最少步数得到最优解。考察一对元素 $A_i,B_i$ ，如果它们分配的符号不同，讨论两种情况：若分配的符号与实际相符（比如 $A_i>B_i$ ，分配 $A_i$ 为正号， $B_i$ 为符号），那么无需改动；若与实际不相符（比如 $A_i>B_i$ ，分配 $A_i$ 为负号， $B_i$ 为正号），那么符号分配就不会是最优解，矛盾。也就是说，当 $A_i,B_i$ 分配的符号不同，就直接忽略。如果 $A_i,B_i$ 分配的符号相同，比如是两个正号，就需要分配了两个负号的 $A_j,B_j$ 进行交换。

假设到达最优解只需要 $k'$ 步，但是题目要求我们需要恰好交换 $k$ 步。若 $k'<k$ ，我们就需要进行 $k-k'$ 次无效交换，即到达最优解后，选取符号相同的 $A_i$ 和 $A_j$ 进行交换。根据抽屉原理，当 $N>2$ 时，在 $A$ 中必有两个位置分配的符号相同；当 $N=2$ 时我们进行特判。

我们分类讨论也可佐证上述的论证。考察两个数对 $(A_i,B_i)$ 和 $(A_j,B_j)$ ，交换后贡献的增量为 $\delta=|A_j-B_i|+|A_i-B_j|-|A_i-B_i|-|A_j-B_j|$ 。若 $N>2$ ，必然存在两个位置 $i,j$ ，有 $A_i>B_i,A_j>B_j$ 或 $A_i<B_i,A_j<B_j$ ，交换后贡献只增不减。若交换后贡献增加，增加的贡献为 $2(\min\{A_i,B_i\}-\max\{A_j,B_j\})$ 或 $2(\min\{A_j,B_j\}-\max\{A_i,B_i\})$ ，两者其实没有区别。

- - $B_i>A_j$ ， $\delta=2(B_i-A_j)$ ；
  - - $A_i>B_j$ ， $\delta=0$ ；
    - $A_i<B_j$ ， $\delta=2(B_j-A_i)$ ；
- - $A_j>B_i$ ， $\delta=2(A_j-B_i)$ ；
  - - $A_i<B_j$ ， $\delta=0$ ；
    - $A_i>B_j$ ， $\delta=2(A_i-B_j)$ 。

将所有 $\min\{A_i,B_i\}$ 和 $\max\{A_i,B_i\}$ 排序。假设 $\min\{A_i,B_i\}$ 的前 $k$ 大与 $\max\{A_i,B_i\}$ 的前 $k$ 小两个区间没有相交部分，就分别依次取前 $k$ 大和前 $k$ 小相减取和即可；若有相交，则取不相交的两端，由于 $\min\{A_i,B_i\}$ 是正贡献， $\max\{A_i,B_i\}$ 是负贡献，取相交位置只会使总贡献变少。图中 $\min\{A_i,B_i\}$ 和 $\max\{A_i,B_i\}$ 都是降序。

图片说明

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2021牛客暑期多校训练营1 G
Date: 2021 June 23rd
Description: Absolute value, Argument
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 500004;
int a[MAX_N], b[MAX_N];
int Max[MAX_N], Min[MAX_N];
int n, k;
ll ans;
int main()
{
    cin >> n >> k;
    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]) << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        Min[i] = min(a[i], b[i]);
        Max[i] = max(a[i], b[i]);
        ans += abs(a[i] - b[i]);
    }
    sort(Min + 1, Min + n + 1, greater<int>());
    sort(Max + 1, Max + n + 1, less<int>());
    for (int i = 1; i <= min(k, n); i++)
    {
        if (Min[i] > Max[i])
        {
            ans += 2 * (Min[i] - Max[i]);
        }
    }
    cout << ans << endl;
    return 0;
}