问题 H: MCC的考验
时间限制: 1 Sec 内存限制: 128 MB
题目描述
MCC男神听说新一期的选拔赛要开始了，给各位小伙伴们带来了一道送分题，如果你做不出来，MCC会很伤心的。
给定一个大小为n的非空整数数组,现在定义一种操作，每一步操作会将该数组中的n-1个数同时加1，问最少进行多少步操作后，可以使得数组里的每一个数字都相等。
例如，一个n为3的数组[1,2,3]，最少进行3步操作后，可以变为[4,4,4]
过程如下：[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
输入
第一行为一个整数n，代表数组个数。1<=n<=1,000,000
第二行为每个数组的数字a[i],1<=a[i]<=1000
输出
输出需要的最少操作数。
样例输入
3 2 3 4
样例输出
3
题目原型：如何用最少的步数使数组的每个元素都相等。
参考算法网站：http://blog.csdn.net/quhaoye/article/details/73251159
解题思路分析
将n-1个数加1，相当于将所有数都加1，再将其中一个数减去1。
将所有数都加1这个操作，其实不会改变任何数的相对大小，也就是所有数两两之间的差都是不会变的，这对于要使所有元素均相等的目标来说没有影响，所以可以忽略这一部分。
那么问题就变成每次选个数减1来达到目标的最小次数。
要使次数最小，而且每次只能将元素减1，故应当把所有数减到与最小值相等。
若n个元素为a(0),a(1),……,a(n-1)，其中最小值为min，则答案为a(0)+a(1)+……+a(n-1)-min*n。
只需求出n个数中的最小值以及它们的和来计算即可，时间复杂度为O(n)。
然后就找到最小的那个值就可以了。
附上代码：
#include <iostream>
#include<math.h>
#include <iomanip>
#include<cstdio>
#include<string>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<stdlib.h>
#include<iterator>
#include<sstream>
#include<string.h>
#include<stdio.h>
using namespace std; int main()
{ unsigned int n;
cin>>n;
int *p; //动态内存分配
p=new int[n];
for(int ii=;ii<n;ii++)
{
cin>>p[ii];//读取数据
}
int count=;
int min=p[];
for(int i=;i<n;i++)
{
if(p[i]<=min)
{
min=p[i];//在循环过程找最小值
}
count=count+p[i];//在循环过程中计算总和
}
//sort(p,0,n-1); //本来相用快排的 但是超时了 cout<<count-min*n;//然后就用公式法就行了
delete []p;
return ;
}