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

题目描述

Given two arrays , with length , you should perform exactly operations in array .

For each operation, choose elements , (​) and swap the positions of and .

Please maximize .

输入描述

The first line of input contains two integers ( ,), describing the length of , and number of operations.

The second line contains integers ().

The third line contains integers ().

输出描述

Output one integer, the maximum answer.

示例1

输入

3 2
1 2 3
3 2 1

输出

4

示例2

输入

3 2
1 2 3
1 2 3

输出

4

示例3

输入

3 1
1 2 3
3 2 1

输出

4

思路

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

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

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

  我们分类讨论也可佐证上述的论证。考察两个数对 和 ，交换后贡献的增量为 。若 ，必然存在两个位置 ，有 或 ，交换后贡献只增不减。若交换后贡献增加，增加的贡献为 或 ，两者其实没有区别。

• 
  • 
    • ，；
    • 
      • ，；
      • ，；
• 
  • 
    • ，；
    • 
      • ，；
      • ，​。

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

代码

/******************************************************************
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;
}