非零段划分

题目 非零段划分

image-39366553

思路分析

可以分三个方向考虑

（1）：y总那样的 水从下往上涨 去分析每个点被淹没时 答案的变化

（2）：反过来 水一开始在最高位 往下退 分析每个点露出时 答案的变化

（3）：从每个点入手 依次加入每个点 利用差分的思想 分析答案变化

对于第一个方向

image-d37e3273

我们可以发现 对于上涨后淹没的每个点 不外乎就4种状态

1.单调上升的（左边比它矮 右边比它高） 那么把它淹没 还是有一个岛（它右边的）只不过体积变小了而已 对答案没影响

2.单调下降的（左边比它高 右边比它矮）那么把它淹没 也是一样 还有左边一个岛 也只是左边这个岛的体积变小了罢了

3.突出（左右都比他矮） 那么把它淹没 原本它是一座岛 现在没了 答案-1

4.凹陷（左右都比他高） 那么把它淹没 原本连成一块的岛就变成了两块 答案+1

对于一种特殊情况

就是如果有很多相邻的 且高度一样的岛 我们无法通过上诉的只比较当前点与左右点来得到

其实可以发现 这些相邻的 高度一样的岛 完全可以看成一个岛 他们共进退、

那么就可以用unique进行一个去重

（unique只是去重相邻元素 不要误解 先sort再unqiue才会把所有重复去除 所以它完美适应该场景）

image-91d8f6db

那么 就可以处理每个点 通过判断它与相邻点的关系

来去对初始状态进行++或--

最后求一次前缀和 在这个过程中用max维护一个最大值 就能得到答案

但是我们可以发现一个问题

初始条件是什么？

理想情况下 当水没涨时 所有的点都在水平面上 形成一个岛 是吧

但是 如果000呢 那不就是0座岛吗 101呢 两座？

这样去写的话 我们还得去对初始状态有个判断 太麻烦了

那么看第二种方式

水平面一开始在最高处 把所有的点都淹没 这样一来 初始状态就确定了 初始为0座岛

好像省事了很多哈

再往下分析

发现也不过是分为4种情况

image-278d7b6c

1.单调上升的（左边比它矮 右边比它高） 那么当它暴露出来 还是有一个岛（它右边的）只不过体积变大了而已 对答案没影响

2.单调下降的（左边比它高 右边比它矮）那么把它暴露出来 也是一样 还有左边一个岛 也只是左边这个岛的体积变大了罢了

3.突出（左右都比他矮） 那么把它暴露出来 原本左右分割的两个岛 现在被它连在一起了 答案-1

4.凹陷（左右都比他高） 那么把它露出 原本没有的岛 现在变成了一座 答案+1

发现其实就是和前一种++，-- 颠倒一下罢了

然后最后的答案应该是求一遍后缀和 （从最后一位开始算 累加起来 过程中找max)

接下来看第三种方式

它利用差分的思想 依次看加入每个点后 对答案的影响

这种比较难想

image-1ef563bd

首先对于第一个0 其实不需要处理

对于9

image-eec06745

可以发现 9一加入的话 任何0~9的水平面都会有一个岛

再看下一个2 它是往下的

image-692765a1

对答案并不构成影响 在0~9的水平面还是只有一个岛露出

再看下一个6

image-5746565f

可以发现 若水平线在2~6 就会加一个岛露出

而0~2 6~9处并不受影响 还是由前面的1影响

我们可以发现一个规律 若出现该元素比上一个元素大 a[i]>a[i-1]（呈单增趋势）时

答案会被影响 即出现一个新的峰 影响怎么表示呢 其实就是 在a[i-1]到a[i]处全加上一个1

那不就是差分吗

只需要在插入每个点的时候 判断与前一个点的关系

如果大于 就在差分数组的b[a[i-1]]处++ b[a[i]]处--即可（无需+1 也是左闭右开）

不信可以继续往后验证

image-76e09d1c

我们可以把它抽象成这样：

image-459a97ec

得到一个差分数组

重新构造前缀和后 再维护找到一个max 那就是答案

代码实现

水面上涨

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;
int n;
int h[N];
int cnt[10010];

int main()
{
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
         cin>>h[i];
         if(h[i])
            sum=1;
    }
    n=unique(h+1,h+n+1)-(h+1);
    h[0]=1,h[n + 1] = 0;

    for(int i=1;i<=n;i++){
        if(h[i-1]<h[i] && h[i+1]<h[i])
            cnt[h[i]]--;
        else if(h[i-1]>h[i] && h[i+1]>h[i])
            cnt[h[i]]++;
    }

    //除了特殊的一开始就全0的情况 不管水平面涨不涨都没岛
    //否则默认所有的山都露在水面上 为一座岛
    //这里不好处理 得重新遍历 不妨放在读入时处理
    int res=0;
    for(int i=0;i<10000;i++){
        sum+=cnt[i];
        res=max(res,sum);
    }

    cout<<res<<endl;
    return 0;
}
//发现这种从下往上找 初始状态都不方便确定
//其实如果出现010这样的数据 感觉这个方法还是会出现问题
//那就是一开始初始为两个岛咯
//很麻烦

水面下降

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;
int n;
int h[N];
int cnt[10010];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
         cin>>h[i];
    }
    n=unique(h+1,h+n+1)-(h+1);
    h[0]=0,h[n + 1] = 0;

    for(int i=1;i<=n;i++){
        if(h[i-1]<h[i] && h[i+1]<h[i])
            cnt[h[i]]++;
        else if(h[i-1]>h[i] && h[i+1]>h[i])
            cnt[h[i]]--;
    }

    int sum=0,res=0;
    //构造后缀和
    for(int i=10000;i>=0;i--){
        sum+=cnt[i];
        res=max(res,sum);
    }

    cout<<res<<endl;
    return 0;
}

从点入手 差分

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;
int n;
int h[N],b[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
         cin>>h[i];
         if(h[i]>h[i-1]){
             b[h[i-1]]++,b[h[i]]--;
         }
    }

    int sum=0,res=0;;
    for(int i=0;i<=10000;i++){
        sum+=b[i];
        res=max(res,sum);
    }

    cout<<res<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 金发姑娘和 N 头牛 🏠 00-刷题理模型 ➡️ _int128