## Overview

• You are given an empty water tank with a capacity of $$C$$ liters.
• Into this tank, the water flows $$x[i]$$ liters for $$t[i]$$ seconds. ($$i = 0$$ to $$n - 1$$)
• You can set the value of output pipe to any maximum output rate $$R$$ (not negative value, but do not have to be an integer) in liters per second.
• Determine the most little output rate limit $$R$$ such that the amount of water in the tank will never exceed $$C$$ liters.

## Explanation

• When it comes to “Find the maximum of the minimum,” we can use Binary Search.
• The returning value can be double, so we apply binary search until the difference between the left and the right value becomes less than the acceptable error.

## Code

const double EPS = 1e-9;
const Inf = 1e9;
double minOutputRate(vector<int> t, vector<int> x, int C) {
int n = (int)t.size();
double left = -EPS, right = Inf, mid;
while (right - left > EPS) {
mid = (right + left) / 2;
double rem = 0.0;
bool ok = true;
for(int i = 0; i < n; i++) {
rem += (x[i] - mid) * t[i];
rem = max(rem, (double)0);
if (rem > C) {
ok = false;
break;
}
}
if (ok)
right = mid;
else
left = mid;
}
return right;
}