Minimize the Maximum
Autumn Tournament (2022)
Submission name: minimize.cpp
Problem summary
You have five nonnegative integers. At most k times, choose a positive integer and reduce it by one. Find the smallest achievable value of the largest integer.
Input
Five integers a, b, c, d, e, followed by k on the next line.
Output
The minimum achievable maximum.
Constraints
0 ≤ a, b, c, d, e, k ≤ 1000000000.
Worked example
Original statement, example 1.
Input
7 3 0 0 0 6
Output
2
Solution analysis
- For a candidate maximum M, each value x greater than M must lose x − M. Thus the minimum required number of operations is need(M) = Σ max(0, x − M).
- A candidate is feasible exactly when need(M) ≤ k. Increasing M never increases the required work, so binary search for the first feasible value between 0 and the original maximum.
- For 7, 3, 0, 0, 0 and k = 6, maximum 2 requires 5 + 1 = 6 operations. Maximum 1 would require 6 + 2 = 8, so the answer is 2.
Why it works
Any solution with maximum at most M must remove at least x − M units from each x > M. Performing exactly those reductions attains that maximum, proving the feasibility test. Feasibility is monotone in M, and binary search maintains the first feasible value inside its interval until only the optimum remains.
Watch out. Use long long for the total required operations, which may reach 5000000000. Operations are optional, so zero remains the answer if k exceeds the sum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
long long values[5];
long long high=0;
for(long long&value:values){
cin>>value;
high=max(high,value);
}
long long k;
cin>>k;
long long low=0;
while(low<high){
long long middle=low+(high-low)/2;
long long needed=0;
for(long long value:values){
needed+=max(0LL,value-middle);
}
// Feasible targets form a suffix of the search interval.
if(needed<=k){
high=middle;
}
else{
low=middle+1;
}
}
cout<<low<<'\n';
}