Water the Flowers
National Olympiad — Regional round (2018 season)
Submission name: flowers.cpp
Problem summary
Water makes each flower grow: q drops add one millimeter to one flower. Given all heights, find the minimum number of drops needed to make every flower equally tall.
Input
n, then n heights in millimeters, then q.
Output
The minimum number of water drops.
Constraints
1 ≤ n ≤ 10000; 1 ≤ height ≤ 10000; 10 ≤ q ≤ 100000000.
Worked example
An independently prepared example for this explanation.
Input
5 10 20 17 12 20 25
Output
525
Solution analysis
- Water can only increase heights. Therefore the final common height must be at least the initial maximum height. Choosing exactly that maximum requires the least growth.
- The total required growth is n·maximum − sumOfHeights. Multiply this by q to obtain the drop count. Store the sum and the final product in long long.
- In the sample the target is 20. The deficits are 10,0,3,8,0 millimeters, totaling 21. At 25 drops per millimeter, 21·25 = 525 drops are needed.
Why it works
Every equalized arrangement has final height H at least the maximum initial height. Its water use is q·(nH−sum), which increases with H. Choosing H equal to the maximum is feasible and minimizes this expression.
Watch out. Do not target the average: flowers cannot shrink. The answer can be near 10¹⁶, so 32-bit arithmetic is insufficient.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
long long sum = 0;
long long maximum = 0;
for (int i = 0; i < n; ++i) {
long long height;
cin >> height;
sum += height;
maximum = max(maximum, height);
}
long long q;
cin >> q;
// Grow every flower to the current maximum, the least possible target.
cout << (n * maximum - sum) * q << '\n';
}