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：

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

输出样例1：

5

输入样例2：

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

输出样例2：

4

输入样例3：

3
1 0 0

输出样例3：

1

输入样例4：

3
0 0 0

输出样例4：

0

题解：

与 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;
}