简答题
偏难
#7562
有多少坑 大雨过后,一些高低不平的地方就会形成积水,俗称为“坑”。这里我们将问题简化为只考虑一段路面的横截面。我们将这一段截面上的土地分割成单位宽度的窄条,测量…
有多少坑
大雨过后,一些高低不平的地方就会形成积水,俗称为“坑”。这里我们将问题简化为只考虑一段路面的横截面。我们将这一段截面上的土地分割成单位宽度的窄条,测量出每个窄条的高度。假设有无穷多的水量从天而降,请你计算一下,这段路面上会形成多少个水坑?坑的最大深度是多少毫米?
时间限制:7000
内存限制:262144
输入
输入第一行给出一个正整数 N(≤ 100000)。随后一行给出 N 个非负整数,为路面横截面总左到右的单位宽度窄条的高度,以毫米为单位,不超过 1000。
输出
输出分两行,第一行输出水坑的个数,第二行输出所有水坑中最大的深度,以毫米为单位。 注意:即使两个相邻的水坑有相同高度的水平面,只要之间有窄条相隔,就算是两个水坑。
样例输入
12
1 4 2 10 7 1 2 1 8 3 1 2
样例输出
3
7
提示
样例说明: 下图给出了样例中得到的水坑示意图。

答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main(){
int n;
cin >> n;
for(int i=0; i<n; i++) cin >> a[i];
int left, right;
//找左边围栏下标
for(left=0; left<n-1 && a[left]<=a[left+1]; left++);//找到左围栏,即左凸起
//找右边围栏下标
for(right=n-1; right>0 && a[right]<=a[right-1]; right--);//右突起
int x, y;
int cnt = 0;
int mmax = 0;
while(1){//从两边到中间
if(left>=right) break;
x = a[left]; //会不断更新
y = a[right];
if(x<y){//左低右高,左向右走
int tmp = 0;//记录跨了多少窄条
while(left<right && a[++left]<=x){//算凹下去多少
tmp++;
if(x-a[left]>mmax) mmax = x-a[left];
}
if(tmp>0) cnt++;//有跨过窄条才算一个水坑
}
else//左高右低,右向左走
{
int tmp = 0;
while(left<right && a[--right]<=y){
tmp++;
if(y-a[right]>mmax) mmax = y-a[right];
}
if(tmp>0) cnt++;
}
}
cout << cnt << endl << mmax;
}</pre>
这道题暂未补解析。