题解
2024-08-07 21:25:57
发布于:上海
5阅读
0回复
0点赞
(这是我能够想到的 最简单的 方法了)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=123456;
ll height[N],n,id,c,l;//height存储读入的高度,n存储高度数量,id存储当前最高点
//c为山脉数量计数器,l为最宽山脉的宽度
ll Mtop[N],len[N];//Mtop存储每座山的最高点,len存储每座山的宽度
int main(){
cin>>n;
for(ll i=1;i<=n+1;i++){
if(i<=n)cin>>height[i];//预留了一个空位n+1,主要是为了下面两行代码操作和更新存储的过程
if(height[i]>height[i-1])id=i;//这里是山坡高度非单调递减的一个过程,需要逐渐更新id
else if(i==id+1)Mtop[c++]=id;//这就是高度非单调递增时的第一个点,此时应当存储最高点
}
if(c>1){//有多座山的情况
len[0]=min_element(height+Mtop[0]+1,height+Mtop[1])-height;
//这里是为了找到第一座山峰高度的最小值,即首山与后山的山谷地区
l=max(l,len[0]);//这里更新最宽山脉的宽度
for(ll i=1;i<c-1;i++){//设有c+1座山,编号0~c那么for循环遍历查找的山编号区间是(0,c+1)
len[i]=min_element(height+Mtop[i]+1,height+Mtop[i+1])-height+1;
//这里是找后一座山脉与该山脉之间的山谷位置
len[i]-=min_element(height+Mtop[i-1]+1,height+Mtop[i])-height;
//这里是找前一座山脉与该山脉之间的山谷位置,并与刚刚的山谷位置作差得到山的宽度
l=max(l,len[i]);//更新l的值
}
len[c-1]=min_element(height+Mtop[c-2]+1,height+Mtop[c-1])-height;
//这里是找倒数第二座山与最后一座山的山谷位置
len[c-1]=n-len[c-1]+1;
//算出最后一座山的宽度
l=max(l,len[c-1]);//更新l的值
}
else l=n;//只有一座山,那么n就是山的宽度
cout<<l<<endl;
return 0;
}
/*
数据样例示意图:
(1)
10
10 20 30 15 24 32 26 21 90 10
1 1 1 1
2 2 2 2 2
3 3 3
(2)
10
10 20 10 15 4 12 26 11 20 10
1 1 1
2 2 2
3 3 3 3
4 4 4
(3)
3
183 591 274
1 1 1
*/
这里空空如也
有帮助,赞一个