题解：AT_joi2019_yo_d 日本沈没 (Japan Sinks)
chenyixuan18
·
·
题解
AT_joi2019_yo_d 日本沈没 (Japan Sinks) 题解
题目大意
题目里说的很清楚了，对岛的定义也很清楚，答案就是海平面到淹没全部陆地时，岛的数量最大值。
思路
我们可以发现，若 a_i 大于 a_{i-1}，说明在 a_i 到
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,t,last,maxn;
map<int,int>mp;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&t);
if(t>last)mp[last]++,mp[t]++;
last=t;
}
for(auto i:mp){
cnt+=i.second;
maxn=max(cnt,maxn);
}
printf("%d",maxn);
return 0;
}
```
此时时间复杂度达到 $O(n\log{n})$，能通过此题。