A30952. 有多少坑大雨过后，一些高低不平的地方就会形成积水，俗称为“坑”。这里我们将问题简化为只考虑一段路面的横截面。我们将这一段截面上的土地分割成单位宽度的窄条，测量出每个窄条的高度。假设有无穷多的水量从天而降，请你计算一下，这段路面上会形成多少个水坑？坑的最大深度是多少毫米？（≤ 100000）。随后一行给出 N 个非负整数，为…
填空题
中等
知识点
题目描述
有多少坑
大雨过后，一些高低不平的地方就会形成积水，俗称为“坑”。这里我们将问题简化为只考虑一段路面的横截面。我们将这一段截面上的土地分割成单位宽度的窄条，测量出每个窄条的高度。假设有无穷多的水量从天而降，请你计算一下，这段路面上会形成多少个水坑？坑的最大深度是多少毫米？
时间限制：7000 内存限制：262144
输入
输入第一行给出一个正整数 N（≤ 100000）。随后一行给出 N 个非负整数，为路面横截面总左到右的单位宽度窄条的高度，以毫米为单位，不超过 1000。
输出
输出分两行，第一行输出水坑的个数，第二行输出所有水坑中最大的深度，以毫米为单位。 注意：
即使两个相邻的水坑有相同高度的水平面，只要之间有窄条相隔，就算是两个水坑。
样例输入
12
1 4 2 10 7 1 2 1 8 3 1 2
样例输出
3
7
提示
样例说明： 下图给出了样例中得到的水坑示意图。
参考答案
#include<iostream>
using namespace std;
int main() {
int n,a[100005],b[100005]= {0}; //b存储水位高度
//存储左右两边最高的
int left[100005],right[100005];
cin>>n;
for(int i=0; i<n; i++) cin>>a[i]; //输入
for(int i=0; i<n; i++) { //找左右最高峰
int left=-1,right=-1;
for(int j=i-1; j>=0; j--) //求左边最高峰
left = max(left,a[j]);
for(int j=i+1; j<n; j++) //求右边最高峰
right = max(right,a[j]);
if(left<=a[i] || right<=a[i]) //没有比自己还高的
b[i] = 0; // 标记作用，没有水坑
else
b[i] = min(left,right); //水位高度取决于短板
}
int s=0,_max=-1;//s统计水坑个数 _max最高水位
for(int i=0; i<n; i++) {
if(b[i+1]==0&&b[i]!=0) { //下一个位置没有水,当前有水
s++;
}
if(b[i]!=0)
_max = max(_max,b[i]-a[i]);
}
cout<<s<<' '<<_max;
return 0;
}
上一题
下一题