问题 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=0;ii<n;ii++) { cin>>p[ii];//读取数据 } int count=0; int min=p[0]; for(int i=0;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 0; }