题目描述(CF1092B)
给定 n 个整数 a1,a2,…,an,n 为偶数。
现在要将它们两两配对,组成 n2 个数对。
ai 和 aj 能够配对,当且仅当 ai=aj。
每次增加操作可以使其中的任意一个数 ai 加一。
请问,要使得 n 个整数能够成功组成 n2 个数对,至少要进行多少次增加操作。
样例
输入样例
6
5 10 2 3 14 5
输出样例
5
数据范围
1≤n≤10^5 ,
1≤ai≤10^4
解题思路
$O(log n)$
- 由题,两两配对要求两数相等,则其实求的是两个数之间的差值;
- 直接对所有数进行一个排序(log n),然后求相邻两数之间的差值,再相加即可(n);
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+7;
int a[N];
int main()
{
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i = 0; i < n; ++i) cin>>a[i];
sort(a, a+n);
int res = 0;
for(int i = 0; i < n; i+=2)
res += (a[i+1] - a[i]);
cout<<res<<endl;
return 0;
}