题目描述

对给定的数组 A 进行如下操作：
任选一个正整数 p，然后将 A 中所有小于 p 的数都变为 0
找到一个合适的 p，使得数组 A 中的非零段个数达到最大。
若输入的 A 所含非零段数已达最大值，可取 p=1，即不对 A 做任何修改
最终需要输出非零段可以达到的最大值

算法1

暴力枚举

时间复杂度 $O(n^2)$
一看数据范围，必然会超时
在csp官网上提交能得70分

C++ 代码

#include <iostream>
using namespace std;
int num[500000];

int main()
{
    int n, p, phrase = 0; // 整数个数，处理数p，段数
    int i, min = 10000, max = 0;

    cin >> n;
    for(i = 0; i < n; i++)
    {
        cin >> num[i];
        if(num[i] < min)
            min = num[i];
        if(num[i] > max)
            max = num[i];
    }

    if(min == max)
    {
        cout << 0;
        return 0;
    }

    int temp;
    bool flag;
    // min = 1 > min ? 1 : min;
    for(p = min; p < max; p++)
    {
        temp = 0;
        flag = true;
        for(i = 0; i < n; i++)
        {
            if(num[i] < p)
            {
                flag = true;
            }
            else
            {
                if(flag)
                {
                    temp += 1;
                    flag = false;
                }
            }
        }
        if (temp > phrase)
            phrase = temp;
    }

    cout << phrase;
    return 0;
}

算法2（100分）

借助岛屿问题

时间复杂度 $O(n)$

考虑p足够大的情况，这时所有的岛都被海水淹没了，只有0个岛屿
然后海平面逐渐下降，岛屿数量开始变化
每当一个凸峰出现，岛屿数就会多一个；
每当一个凹谷出现，原本相邻的两个岛屿就被这个凹谷连在一起了，岛屿数减少一个
可以使用数组cnt[]，cnt[i] 表示海平面 下降 到i时，岛屿数量的变化

这样，数组元素cnt[i]中存储的就是该元素被替换为0时，划分数变化的差分值
最大值则只需要从其前缀和（程序中实际为 后缀和）中找出最大值

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 500004, M = 10004;
int n, a[N], cnt[M];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    a[0] = a[n + 1] = 0; // 边界
    n = unique(a, a + 2 + n) - a;
    // 去重后不存在相邻处相等的情况
    for(int i = 1; i < n; i++)
    {
        if(a[i - 1] < a[i] && a[i] > a[i + 1]) // 凸峰
            cnt[a[i]]++;
        else if(a[i - 1] > a[i] && a[i] < a[i + 1]) // 凹谷
            cnt[a[i]]--;
    }

    int res = 0, sum = 0;
    for(int i = M; i; i--)
    {
        sum += cnt[i];
        res = max(res, sum);
    }
    printf("%d\n", res);
    return 0;
}

算法3（100分）

和算法2类似 使用差分+前缀和

时间复杂度 $O(n)$

如果 $a[i] > a[i-1]$
意味着当p取到 $a[i-1]+1$ 到 $a[i]$ 之间的值时，非零段+1
使用数组cnt[]，cnt[i] 表示p从i-1上升到i时，非零段数量的变化
从正向前缀和中找出最大值就是所要的结果

C++ 代码

#include <iostream>
using namespace std;

const int N = 500004;
const int M = 10004;
int a[N], cnt[N];

int main()
{
    int n, phrase = 0; // 整数个数，段数
    int i;

    cin >> n;
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if(a[i] > a[i-1])
        {
            cnt[a[i-1]+1]++;
            cnt[a[i]+1]--;
        }
    }

    int sum = 0;
    for(i = 1; i < M; i++)
    {
        sum += cnt[i];
        phrase = max(phrase, sum);
    }

    printf("%d\n", phrase);
    return 0;
}