AcWing 3580. 整数配对(贪心)
原题链接
中等
作者:
殇ベ_11
,
2021-06-07 15:07:54
,
所有人可见
,
阅读 250
题目描述
给定 n 个整数 a1,a2,…,an,n 为偶数。
现在要将它们两两配对,组成 n2 个数对。
ai 和 aj 能够配对,当且仅当 ai=aj。
每次增加操作可以使其中的任意一个数 ai 加一。
请问,要使得 n 个整数能够成功组成 n2 个数对,至少要进行多少次增加操作。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数,表示所需最少操作次数。
数据范围
1≤n≤105,
1≤ai≤104
样例
输入样例1:
6
5 10 2 3 14 5
输出样例1:
5
输入样例2:
2
1 100
输出样例2:
99
算法1
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6;
int n;
int a[N];
bool st[N];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
memset(st,false, sizeof(st));
sort(a + 1,a + n + 1);
int idx = 0;
int res = 0;
for(int i = 1;i <= n;i ++){
if(a[i] == a[i + 1] && st[i] == false && st[i + 1] == false){
st[i] = st[i + 1] = true;
idx ++;
}
else if(a[i] != a[i + 1] && st[i] == false && st[i + 1] == false){
st[i] = st[i + 1] = true;
res += a[i + 1] - a[i];
idx++;
}
if(idx >= n/2){
printf("%d",res);
return 0;
}
}
}