首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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>
这道题暂未补解析。