AcWing 4306：序列处理 ← 贪心算法
【题目来源】
https://www.acwing.com/problem/content/4309/
【题目描述】
给定一个长度为 n 的整数序列 a1,a2,…,an。
我们可以对该序列进行修改操作，每次操作选中其中一个元素，并使其增加 1。
现在，请你计算要使得序列中的元素各不相同，至少需要进行多少次操作。
【输入格式】
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
【输出格式】
一个整数，表示所需的最少操作次数。
【输入样例1】
4
1 3 1 4
【输出样例1】
1
【输入样例2】
5
1 2 3 2 5
【输出样例2】
2
【算法分析】
基于贪心思想，首先对数组元素进行排序，然后判定后一个数是否大于前一个数。
若为否，则后一个数不断加 1 并对操作次数进行计数。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
const int maxn=10005;
int a[maxn];
int ans;
int main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=2; i<=n; i++) {
while(a[i]<=a[i-1]) {
ans++;
a[i]++;
}
}
cout<<ans<<endl;
return 0;
}
/*
in:
5
1 2 3 2 5
out:
2
*/
【参考文献】
https://www.acwing.com/solution/content/92235/
https://www.acwing.com/solution/content/94995/