题目描述

给定 n 个整数 a1,a2,…,an，n 为偶数。

现在要将它们两两配对，组成 n/2 个数对。

ai 和 aj 能够配对，当且仅当 ai=aj。

每次增加操作可以使其中的任意一个数 ai 加一。

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

样例

输入样例1：
6
5 10 2 3 14 5
输出样例1：
5

算法1

对于每个输入的数记录到bool数组中，每次取反，所以如果一个数出现了偶数次则没有影响，最后bool数组中值为true的元素就是需要配对的元素，按序遍历并且求下标差即可，时间复杂度为O(n+m)

时间复杂度

O(n+m)

C++ 代码

#include <iostream>
using namespace std;
const int N =1e5+5, M = 1e4+5;
int n, a[N];
bool b[M];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        b[a[i]] = !b[a[i]];
    }
    bool tag = false;
    int id = 0, res = 0;
    for(int i = 0; i < M; i ++)
    {
        if(b[i]){
            if(tag){
                tag = false;
                res += i-id;
            }
            else{
                tag = true;
                id = i;
            }
        }
    }
    cout << res;
    return 0;
}