第一题：

题目描述：

给你N棵树，每棵树都有一个高度a[i]，  （N和a[i]都是一百万数量级）
你每次可以施展魔法让其中一棵树不生长而其它树高度都加一，
问最少几次魔法可以使得所有树一样高。

分析：

对于次高的树来说，想要达到最高的高度，我们只需要施展【他们高度差值】的次数魔法。

例如两棵树的高度是6和4，那么只需要2次让6不动，4就可以变成6.

当然这只是对于最高的树只有一棵来说的，若是有m棵最高的树，则次高树想变成最高树需要施展【m*高度差值】次数的魔法。

例如三棵树6 6 4，想变成相等高度的树，需要2*2=4次，具体过程是【6 7 5】 【7 7 6】 【7 8 7】【8 8 8】

当然这里次高树的棵树是没有影响的。

例如次高树也有两颗，但是答案不变，假如4棵树6 6 4 4，具体过程【6 7 5 5】【7 7 6 6】【8 7 7 7】【8 8 8 8】

有了把次高树变成最高树的策略，那所有问题都解决了，因为次高树变成了最高树，那么再考虑次次高树，次次次高树即可，所有的都可以由这一个策略算出来。

这里需要注意的是，魔法只会针对最高树使用，因为遏制其他的树生长只会让差值越来越大，与我们的目的相反。

解法：

先把N棵树按高度排序，并且去重，统计每个高度树的棵树。

在解决最高树和次高树的过程中，我们要维护以下几个关键的有用的量：

一、次高树与最高树的高度差： int cha=maxx-(b[i]+ans);

随着越来越多的树变成了最高树的高度，次高树的高度也在随着变化，他们变成了【本身高度+魔法次数】的高度。

二、使用魔法的次数    ans+=cha*m;

如上述分析，次高树想变成最高树需要施展【m*高度差值】次数的魔法。

三、最高树的高度   maxx+=cha*(m-1);

最高树的高度变化与普通树不同，对于除了最高树之外的普通树来说，魔法施展几次，他们就会增加几，因为他们从不被遏制生长。

但是最高树会被魔法遏制，所以在次高树变成最高树的时候，最高树的高度只是增加了【差值次数*(最高树棵树-1)】的高度。

这里可以参照分析的例子【6 6 4 4】，经过4次变化，达到了【8 8 8 8】的高度，两棵高度为4的树生长高度对应魔法次数4，但是最高树因为被遏制只生长了2，也就是【差值次数*(最高树棵树-1)】的高度。

四、最高树的棵树   m+=c[i];

次高树变成了最高树之后，要统计入答案。

维护了这4个量，我们就可以O(n)时间求出答案。最重要的是理解最高树和普通的树在高度变化过程中的数量差异。

代码：

	
	

		
		

			
			

				
			

		

		

			
			

				#include<iostream> 
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				#include<cstdio>  
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				#include<algorithm> 
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				using namespace std;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int a[1000050];
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int b[1000050];
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int c[1000050];
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int n;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				bool cmp(int x,int y){
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				return x>y;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				}
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int main(){
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				cin>>n;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				for (int i=1; i<=n; i++){
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				scanf("%d",&a[i]);
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				}
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				//排序去重  
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				sort(a+1,a+n+1,cmp);
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				b[1]=a[1];
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				c[1]=1;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int p=1;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				for (int i=2; i<=n; i++){
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				if (a[i]!=b[p]){
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				p++;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				b[p]=a[i];
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				c[p]=1;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				} else c[p]++;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				}
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int maxx=b[1]; //最大值  
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int m=c[1]; //最大值个数  
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				long long ans=0;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				for (int i=2; i<=p; i++){
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				int cha=maxx-(b[i]+ans);
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				ans+=cha*m;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				maxx+=cha*(m-1);
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				m+=c[i];
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				}
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				cout<<ans<<endl;
			

		

	

	

		
		

			
			

				
			

		

		

			
			

				}