leetcode-go/poj/1877.flooded/main.cc

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>

using std::sort;

const char fmt[] = "Region %d\nWater level is %.2f meters.\n%.2f percent of the region is under water.\n";
const int N = 30;
const int SQR = 100;

int hei[N * N];
int sum[N * N];

int m, n, mn, vol;

int first_ge() {
  int s = 0, e = mn - 1;
  while (s <= e) {
    int m = s + (e - s) / 2;
    if (sum[m] < vol) {
      s = m + 1;
    } else {
      e = m - 1;
    }
  }
  return s;
}

int main() {
  int rid = 1;
  while (scanf("%d %d", &m, &n) != EOF) {
    if (m == 0 && n == 0) break;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        scanf("%d", &hei[i * n + j]);
    scanf("%d", &vol);
    mn = m * n;
    sort(hei, hei + mn);
    for (int i = 0; i < mn - 1; i++) {
      sum[i] = (hei[i + 1] - hei[i]) * SQR * (i + 1);
      if (i != 0) sum[i] += sum[i - 1];
    }
    sum[mn - 1] = INT_MAX;
    int i = first_ge();
    double lv = hei[i];
    vol = i == 0 ? vol : vol - sum[i - 1];
    lv += double(vol) / ((i + 1) * SQR);
    printf(fmt, rid++, lv, (i + 1) * 100 / double(mn));
  }
  return 0;
}