4007-非零段划分

#personal/blog #algorithm/差分

4007. 非零段划分 - AcWing题库

题目描述

关系

0001-2014-岛

内容

$A_{1}, A_{2}, \dots, A_{n}$ 是一个由 $n$ 个自然数（非负整数）组成的数组。

我们称其中 $A_{i}, \dots, A_{j}$ 是一个非零段，当且仅当以下条件同时满足：

$1 \leq i \leq j \leq n$ ；
对于任意的整数 $k$ ，若 $i \leq k \leq j$ ，则 $A_{k} > 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}, \dots, A_{n}$ 。

输出格式

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

数据范围

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

输入样例 1：

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

输出样例 1：

样例 1 解释

$p = 2$ 时， $A = [3, 0, 2, 0, 0, 2, 0, 4, 5, 0, 2]$ ， $5$ 个非零段依次为 $[3]$ 、 $[2]$ 、 $[2]$ 、 $[4, 5]$ 和 $[2]$ ；此时非零段个数达到最大。

输入样例 2：

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

输出样例 2：

样例 2 解释

$p = 12$ 时， $A = [0, 0, 20, 0, 0, 0, 0, 15, 0, 20, 0, 0, 0, 15]$ ， $4$ 个非零段依次为 $[20]$ 、 $[15]$ 、 $[20]$ 和 $[15]$ ；此时非零段个数达到最大。

输入样例 3：

3
1 0 0

输出样例 3：

样例 3 解释

$p = 1$ 时， $A = [1, 0, 0]$ ，此时仅有 $1$ 个非零段 $[1]$ ，非零段个数达到最大。

输入样例 4：

3
0 0 0

输出样例 4：

样例 4 解释

无论 $p$ 取何值， $A$ 都不含有非零段，故非零段个数至多为 $0$ 。

问题分析

最初思路

我们并不关心，究竟有多少高，只关系某个时刻，是否能够大于 0. 也就是与旁边元素的关系。