[C++知识库]小李发奖金（c++）

题目描述

当然打台球只是小李的休闲娱乐活动，对待他的本职工作，他还是非常兢兢业业的。但是小李的老板是个周扒皮，每次都想克扣小李的工资和奖金，甚至制定出非常奇葩的规则。
又到了每年发年终奖的时候了，今年老板的规则是这样的：给你n个数，每次你可以对任意一个数加1，直到所有的数都不相等为止，每加一次都要花费一定数额的费用。为了小李的幸福生活，聪明的你可否帮助小李，让他尽量少扣钱。

输入

第一行n（1<=n<=30000），表示共有n个数。
第二行共n个用空格隔开的非负整数ai（ai<=1000000）。

输出

仅一个整数，表示加到让每个数都不相等的最少次数。

样例输入?Copy

4 
1 1 3 2

样例输出?Copy

3

提示

让1+1+1+1 = 4，给定的数字变成4,1,3,2。?

思路：

先将输入的数组进行排序，为了降低时间用sort函数进行排序，其实也可以冒泡排序、快速排序、插空排序、桶排序进行排序，在完成排序后来比较数组中的前后元素的关系。

代码如下

#include<bits/stdc++.h>
using namespace std;


int main()
{
	int n,i,sum=0；
	cin>>n;
	int a[30005];//数组开的大一些
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);//先用sort函数对序列进行排序，然后要解决的就是排序之后相邻的两项相同的情况 
	for(i=0;i<n-1;i++)
	{
		if(a[i]<=a[i+1]-1)//如果这一项和他的下一项的值差距>=1,则跳过此循环 
		{
			continue;
		}
		else//前后两项相同的情况，对其进行处理 
		{
			sum=sum+a[i]-a[i+1]+1;//核心 
			a[i+1]=a[i]+1;
		}
	 } 
	cout<<sum<<endl;
	
	return 0;
}