问题描述
p815原题链接:UVaOJ 815 - Flooded!
相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-10
解法一:模拟 + 排序
将所有区域按照海拔 ele 排序后,模拟洪水的淹没规律:先从海拔最低的 1 个区域开始淹 ele[1] - ele[0] 个 $10 \times 10$ 立方(为了简化讨论,假设区域面积相关的计算放到最后进行);然后从现在海拔最低的 2 个区域分别开始淹 ele[2] - ele[1] 个立方... 极限情况下(水很多),这 m*n 个区域被填满后,水面整体上升。那么一种解决思路是,统计一下每个区域刚成为海平面(也即目前的最低区域)时,下面总共有多少水,记为 under[i]. 对于总的降水量 collect_water, 只需要找到其所在的 under 区间就行,这样问题就被简化成了一个给定长方体体积和底面面积,求高度的简单问题。具体逻辑请看代码。
这题可以节省更多的内存空间,但代码读起来不那么直观,优先保证可读性。
需要注意的容易 WA 地方:
- 整型到浮点数转换和计算顺序不对的话,可能会造成精度损失;
- 输出默认带一个空行,而不是多个 Cases 之间带空行。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#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; } |
1 |
#TODO |