AcWing 3580.整数配对

题目详情

给定 \(n\) 个整数 \(a_1,a_2,…,a_n\), \(n\) 为偶数。

现在要将它们两两配对，组成 \(n2\) 个数对。

\(ai\) 和 \(a_j\) 能够配对，当且仅当 \(a_i=a_j\)。

每次增加操作可以使其中的任意一个数 \(a_i\) 加一。

请问，要使得 \(n\) 个整数能够成功组成 \(\frac{n}{2}\) 个数对，至少要进行多少次增加操作。

输入格式

第一行包含整数 \(n\)。

第二行包含 \(n\) 个整数 \(a_1,a_2,…,a_n\)。

输出格式

一个整数，表示所需最少操作次数

数据范围

\[1\leq n\leq10^5\], \(1\leq a_i\leq10^4\)

输入样例1

6
5 10 2 3 14 5

输出样例1

5

输入样例2

2
1 100

输出样例2

99

题目思路

本题中考虑到需要使用最小的修改可以实现所有的整数配对，故实际上最优解一定是将某个数字a[i]修改为离他最近的一个数字a[j]。

我们可以将排序好的所有数字放到一个数轴上，就可以看到下面的情况

image.png

为了使得我们的修改量最少，即数轴上每个点找到和他配对的一个点所需移动的总距离最小，此时我们需要尽量少地越过其他的点，故可以证明对于每个a[i]都必须找其相邻的点进行配对。

假设我们使用蓝色的方法进行配对，此时a[1]必须越过a[2]和a[3]寻找与其配对的点，此时并非最小。

image-20210527191959278

同样对于后面的每一个点均适用于该种情况。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    
    int res = 0;
    for (int i = 1; i <= n; i += 2)
    {
        res += abs(a[i + 1] - a[i]);
    }
    
    cout << res;
}