思路:
由题意我们可以知道我们需要进行离散化并进行求山峰与山谷的贡献度
解释一下:当两边均小于是就是山峰当两边均大于时便是山谷
我们可以动态模拟一下水涨的过程,当水恰好涨到某个高度时
这个时间段相当于上次会减小几个长度为该高度的山峰,增加改长度的山谷
注意:这里是减小山峰,增加山谷,应为当浴了山峰会减小一个,而浴了山谷会增加一个
我们可以发现在上次高度到这次高度之间状态是一样的,不会变化
所以这里不能一一枚举(太慢了)应该用离散化依次枚举每一个高度,所以也用到缩点
但是!!!这样代码实在太长了
-------------------------分割线---------------------------------------------
我们再进行优化一下:我们发现当我们依次看每个状态时,当某个点大于前一个点时
当水到两者之间会贡献一个岛此时加一(注意这里不再与上一个进行比较,单纯的计算)
而当过了此点后会浴过一个岛,此时应该减一
注意我们不用管后面的那个点了,因为:当后面点小于此点,状态是一样的
而当后面点大于此点时我们过了这个点会进行-1,后面点会进行加1也就是两岛合并
并不会进行重复计算,所以这种优化是可行的
但重要的是我们进行加1减1后要进行前缀和,这里要进行排序后的
map刚好解决了我们的需要,map会提供排序功能
C++ 代码
#include<iostream>
#include<map>
using namespace std;
const int N=1e5+10;
int a[N];
int n;
map<int ,int >pd;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>a[i-1])
{
pd[a[i-1]]++;
pd[a[i]]--;//注意这里是pd[a[i]]--不是pd[a[i]+1]--,因为水浴到a[i]岛就没了
}
}
long long res=0,sum=0;
for(auto i:pd)
{
sum+=i.second;
res=max(res,sum);
}
cout<<res;
}