UVaOJ 815 - Flooded!

问题描述

解法一：模拟 + 排序

将所有区域按照海拔 ele 排序后，模拟洪水的淹没规律：先从海拔最低的 1 个区域开始淹 ele[1] - ele[0] 个 $10 \times 10$ 立方（为了简化讨论，假设区域面积相关的计算放到最后进行）；然后从现在海拔最低的 2 个区域分别开始淹 ele[2] - ele[1] 个立方... 极限情况下（水很多），这 m*n 个区域被填满后，水面整体上升。那么一种解决思路是，统计一下每个区域刚成为海平面（也即目前的最低区域）时，下面总共有多少水，记为 under[i]. 对于总的降水量 collect_water, 只需要找到其所在的 under 区间就行，这样问题就被简化成了一个给定长方体体积和底面面积，求高度的简单问题。具体逻辑请看代码。

这题可以节省更多的内存空间，但代码读起来不那么直观，优先保证可读性。

需要注意的容易 WA 地方：

整型到浮点数转换和计算顺序不对的话，可能会造成精度损失；
输出默认带一个空行，而不是多个 Cases 之间带空行。

#include <bits/stdc++.h>

using namespace std;

int main() {

  int m, n, num_region = 0;
  while (cin >> m >> n && (m && n)) {
    cout << "Region " << ++num_region << endl;

    vector<int> ele(m * n, 0);  // The elevation
    for (int i = 0; i < m * n; ++i) cin >> ele[i];
    sort(ele.begin(), ele.end());

    double collect_water, water_level, under_percent;
    cin >> collect_water;

    int start = -1;  // Sea-level block index - [0, m*n)
    vector<int> under(m * n, 0);  // Water under the elevation
    for (int i = 0; i < m * n; ++i) {
      under[i] = i ? under[i - 1] + (ele[i] - ele[i - 1]) * i : 0;
      if (collect_water > under[i] * 100) start++;
    }
    water_level =
        (collect_water - under[start] * 100) / ((start + 1) * 100) + ele[start];
    under_percent = 100.0 * (start + 1) / (m * n);
    cout << fixed << setprecision(2) 
         << "Water level is " << water_level << " meters.\n"
         << under_percent << " percent of the region is under water.\n"
         << endl;
  }

  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {

int m, n, num_region = 0;

while (cin >> m >> n && (m && n)) {

cout << "Region " << ++num_region << endl;

vector<int> ele(m * n, 0); // The elevation

for (int i = 0; i < m * n; ++i) cin >> ele[i];

sort(ele.begin(), ele.end());

double collect_water, water_level, under_percent;

cin >> collect_water;

int start = -1; // Sea-level block index - [0, m*n)

vector<int> under(m * n, 0); // Water under the elevation

for (int i = 0; i < m * n; ++i) {

under[i] = i ? under[i - 1] + (ele[i] - ele[i - 1]) * i : 0;

if (collect_water > under[i] * 100) start++;

}

water_level =

(collect_water - under[start] * 100) / ((start + 1) * 100) + ele[start];

under_percent = 100.0 * (start + 1) / (m * n);

cout << fixed << setprecision(2)

<< "Water level is " << water_level << " meters.\n"

<< under_percent << " percent of the region is under water.\n"

<< endl;

}

return 0;

}

#TODO

#TODO

AOAPC II UVaOJ