4007.非零段划分

4007. 非零段划分

题目描述：

$ A_1,A_2,⋯,A_n $ 是一个由 nn 个自然数（非负整数）组成的数组。

我们称其中 $ A_i,⋯,A_j $ 是一个非零段，当且仅当以下条件同时满足：

$ 1\le i\le j\le n $ ；
对于任意的整数 $ k $ ，若 $ i\le k\le j $ ，则 $ A_k \gt 0 $ ；
$ i=1 $ 或 $ A_{i−1}=0 $ ；
$ j=n $ 或 $ A_{j+1}=0 $ 。

下面展示了几个简单的例子：

$ A=[3,1,2,0,0,2,0,4,5,0,2] $ 中的 $ 4 $ 个非零段依次为 $ [3,1,2]、[2]、[4,5] $ 和 $ [2] $ ；
$ A=[2,3,1,4,5] $ 仅有 $ 1 $ 个非零段；
$ A=[0,0,0] $ 则不含非零段（即非零段个数为 $ 0 $ ）。

现在我们可以对数组 $ A $ 进行如下操作：任选一个正整数 $ p $ ，然后将 $ A $ 中所有小于 $ p $ 的数都变为 $ 0 $ 。

试选取一个合适的 $ p $ ，使得数组 $ A $ 中的非零段个数达到最大。

若输入的 $ A $ 所含非零段数已达最大值，可取 $ p=1 $ ，即不对 $ A $ 做任何修改。

输入格式

输入的第一行包含一个正整数 $ n $ 。

输入的第二行包含 $ n $ 个用空格分隔的自然数 $ A_1,A_2,⋯,A_n $ 。

输出格式

仅输出一个整数，表示对数组 $ A $ 进行操作后，其非零段个数能达到的最大值。

数据范围

$ 70\% $ 的测试数据满足 $ n\le 1000 $ ；
全部的测试数据满足 $ n\le 5 \times 10^5 $ ，且数组 $ A $ 中的每一个数均不超过 $ 10^4 $ 。

输入样例1：

1 2	11 3 1 2 0 0 2 0 4 5 0 2

输出样例1：

输入样例2：

1 2	14 5 1 20 10 10 10 10 15 10 20 1 5 10 15

输出样例2：

输入样例3：

1
2

3
1 0 0

输出样例3：

输入样例4：

1
2

3
0 0 0

输出样例4：

题解：

与 2014.岛类似 2014.岛 | Luobuyu’s Blog

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 5e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
pair<int, int> q[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        // read(a[i]);
        cin >> a[i];
    }
    // 去重
    n = unique(a + 1, a + 1 + n) - a - 1;

    // 离散化是需要把id进行映射，将 a[i] 比较大的数映射为比较小的
    // 可以使用 map 进行处理，分配 map.size() + 1
    for (int i = 1; i <= n; i++)
    {
        q[i] = {a[i], i};
    }
    sort(q + 1, q + 1 + n);
    bool flag = 0;
    int minx = INF;
    int maxx = -1;
    for (int i = 1; i <= n; i++)
    {
        minx = min(minx, a[i]);
        maxx = max(maxx, a[i]);
    }
    if (minx == maxx)
    {
        cout << 0 << endl;
        return 0;
    }
    int cnt = 1;
    int ans = 1;
    a[0] = a[n + 1] = 0;
    for (int i = 1; i <= n; i++)
    {
        int id = q[i].second;
        if (a[id] > a[id - 1] && a[id] > a[id + 1])
            cnt--;
        else if (a[id] < a[id - 1] && a[id] < a[id + 1])
            cnt++;
        // 其他两种是同构的，而且是cnt保持不变
        if (q[i].first != q[i + 1].first)
            ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}