MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 815 - Flooded!
AOAPC II

UVaOJ 815 - Flooded!

Chai
2021-11-24 0:00:00在线评测阅读 391

问题描述

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 之间带空行。
C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz