Equalizing by incrementing all but one
National Olympiad — National round
Submission name: seq.cpp
Problem summary
In one operation choose one position and increase every other element by 1. Find the minimum operations needed to make all array elements equal.
Input
N, followed by N positive integers.
Output
The minimum operation count.
Constraints
1 ≤ N ≤ 1,000,000; 1 ≤ a[i] ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
4 2 2 5 3
Output
4
Solution analysis
- Subtracting 1 from every element after each operation does not change equality. The operation is thus equivalent to decreasing the chosen element by 1.
- All values must be reduced to at most the original minimum. Choosing that minimum requires the fewest decreases.
- Return sum(a)−N·min(a).
Why it works
If the common reduced target is t, the operation count is sum(a)−Nt and feasibility requires t≤min(a). Maximizing t minimizes the count; t=min(a) is achievable.
Complexity: O(N) time and O(1) space.
Watch out. An operation does not increment the selected element. A one-element array already has equal elements.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: If the common reduced target is t, the operation count is sum(a)−Nt and feasibility
// requires t≤min(a). Maximizing t minimizes the count; t=min(a) is achievable.
#include<iostream>
#include<algorithm>
#include<tuple>
#include<climits>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
long long sum=0,mn=LLONG_MAX;
for(int i=0;i<n;i++){
long long x;
cin>>x;
sum+=x;
mn=min(mn,x);
}
cout<<sum-n*mn<<'\n';
}