当前位置：首页 > news >正文

东方博宜24年8月-C组 - 屋顶

news 来源：原创 2024/9/20 19:22:23

本解析禁止用于商业用途

禁止在未经许可的情况下转载

本篇仅在CSDN发布

官方解析请访问24年东方博宜OJ编程月赛评讲课 - 网易云课堂

题目描述

小 A 在奥运会期间，前往巴黎观看奥运会的相关赛事。
在某项体育比赛中，他被场馆的屋顶吸引了，这个屋顶不同于普通的屋顶，在平坦的屋顶上，设计师使用特殊材料制作的边长为 1 米正方体，设计出了各种造型。
由于正方体的高矮不一，下雨时，屋顶会有一定的积水，这些积水会被保留在屋顶，用于场馆内的绿植灌溉。
下图给出了一个宽度为 8 的屋顶的截面图。在截面图中，我们可以看到，白色的方块是特殊材料制作的正方体，蓝色矩形，是下雨后，屋顶上的积水区域。图中积水区域的总面积为 9 平方米。

给定 N 个整数，分别代表宽度为 N 的屋顶，每个位置上正方体的高度，请你编程计算出，在屋顶截面图中，积水区域的最大总面积是多少？

输入

输入两行，第一行输入一个整数 N，屋顶的宽度。
第二行包含 N 个整数，表示每个位置立方体的高度。

输出

一个整数，表示积水区域的最大总面积。

样例

输入

8
2 4 0 1 2 3 0 3

输出

输入

7
19 13 3 20 13 8 25

输出

输入

11
12 0 30 7 29 17 25 18 9 20 8

输出

说明

数据范围
对于 10% 的数据，满足 1≤N≤100，每个位置的立方体高度单调递增。
对于另外 60% 的数据，满足 1≤N≤1000，每个位置的立方体高度没有明显的规律。
对于 100% 的数据，满足 3≤n≤100000 ，每个位置的立方体的高度，均在 [0,1000] 的范围内。

代码

使用双指针法来计算屋顶的积水区域面积：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int maxRainwaterTrapped(const vector<int>& heights) {int n = heights.size();if (n < 3) return 0;int left = 0, right = n - 1;int left_max = heights[left], right_max = heights[right];int water_trapped = 0;while (left < right) {if (left_max < right_max) {left++;if (heights[left] < left_max) {water_trapped += left_max - heights[left];} else {left_max = heights[left];}} else {right--;if (heights[right] < right_max) {water_trapped += right_max - heights[right];} else {right_max = heights[right];}}}return water_trapped;
}int main() {int N;cin >> N;vector<int> heights(N);for (int i = 0; i < N; ++i) {cin >> heights[i];}cout << maxRainwaterTrapped(heights) << endl;return 0;
}

解释

初始化：
- left 和 right 分别指向数组的两端。
- left_max 和 right_max 分别初始化为数组两端的高度。
- water_trapped 用于累计积水面积。
双指针移动：
- 比较 left_max 和 right_max，优先处理较小的那一侧。
- 如果当前位置的高度小于 left_max 或 right_max，则可以计算积水面积。
- 更新 left_max 或 right_max，并移动指针。
计算积水面积：
- 如果当前位置的高度小于 left_max，则积水面积为 left_max - heights[left]。
- 如果当前位置的高度小于 right_max，则积水面积为 right_max - heights[right]。
输出结果：
- 最终输出 water_trapped，即积水区域的最大总面积。