TopCoder SRM 676 Div.1 Easy: Water Tank

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;
}