本文共 855 字，大约阅读时间需要 2 分钟。

 2014宁波市中小学生程序设计竞赛 复赛 第3题 小李发奖金

时间限制: 1 Sec  内存限制: 128 MB

题目描述

　　当然打台球只是小李的休闲娱乐活动，对待他的本职工作，他还是非常兢兢业业的。但是小李的老板是个周扒皮，每次都想克扣小李的工资和奖金，甚至制定出非常奇葩的规则。

　　又到了每年发年终奖的时候了，今年老板的规则是这样的：给你n个数，每次你可以对任意一个数加1，直到所有的数都不相等为止，每加一次都要花费一定数额的费用。为了小李的幸福生活，聪明的你可否帮助小李，让他尽量少扣钱。

输入

　　第一行n，表示共有n个数。

　　第二行共n个用空格隔开的非负整数ai。

 

【样例说明】

　　让1+1+1+1 = 4，给定的数字变成4,1,3,2。【数据规模】 　　30%的数据，1<=n<=10 　　60%的数据，1<=n<=1000 　　80%的数据，1<=n<=30000，ai<=1000， 　　100%的数据，1<=n<=30000， ai<=1000000。

输出

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

样例输入

41 1 3 2

样例输出

3

徐不可说：先用sort排序 对于相等的数据如果采用for循环往后能插的空 进行逐个比较 时间复杂度应该会很高 1000000的数据过不了 采用做差值的方法比较好

#include
   
    #include
    
     using namespace std;int a[30005];int main(){	int n,sum=0;	cin>>n;	for(int i=0;i
     
      >a[i];	sort(a,a+n);	a[n]=1000005;	for(int i=0;i
      
       =a[i]) continue;		else 		{		sum=sum+a[i]-a[i+1]+1;		a[i+1]=a[i]+1;	    }	}	cout<
       
        <
       
      
     
    
   

 

转载地址：http://wotgn.baihongyu.com/