202109-2
非零线段划分-题目描述
A1,A2,⋯,An 是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段，当且仅当以下条件同时满足：
1≤i≤j≤n；
对于任意的整数 k，若 i≤k≤j，则 Ak>0；
i=1 或 Ai−1=0；
j=n 或 Aj+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 个用空格分隔的自然数 A1,A2,⋯,An。
输出格式
输出到标准输出。
仅输出一个整数，表示对数组 A 进行操作后，其非零段个数能达到的最大值。
输入
11
3 1 2 0 0 2 0 4 5 0 2
输出
5
说明/提示
样例解释
p=2时，A=[3,0,2,0,0,2,0,4,5,0,2]，5个非零段依次为[3]、[2]、[2]、[4,5] 和 [2],此时非零段个数达到最大。
子任务
70%的测试数据满足n < 1000
全部的测试数据满足n < 5 * 10^5 ，且数组中的每一个数均不超过10 ^ 4。
思路解析
把它看作若干个岛屿，水面从最高点逐步下降。
暴力模拟的话，5 * 10 ^ 5的陆地长度，10^4的水面高度
每个高度的水面都从头遍历一遍所有的陆地，然后再寻找遍历结果的最大值
那乘起来就是10^9，肯定超时。
所以，最好能只过一遍，只计算当水面下降时，哪个位置的岛屿会露出来/沉下去。
我们用1 4 2 3 9 0 9 0 0 8 1 3 0举例
你看那个4，当水面从4降低到3的时候，他就会露出来。
所以，我们用类似于差分的思想
假设待处理数组为ls，把ls[i]分为三种：
1.咋都不会改变岛屿数量。中间值就可以，比如1，2，3中间的2，咋都不会变
2.可能增加岛屿数量。比如1,3,1，中间的3，水面小于1的时候3不影响，1-3的时候3是一个岛屿，大于等于3的时候不影响
3.可能减少岛屿数量。比如3,1,3，中间的1，同上。
所以，我们不难看出，ls[i]只会改变当水涨到 ls[i] 的值，且情况1不会改变，情况2，3分别会+1/-1。
因此，我们新建一个列表，暂且就叫它ls2，专门用来存储当水涨到ls[i]时，岛屿总数改变的数量。
不难看出，ls2枚举值的最大值等于ls[i]的最大值。
所以，对于待处理数组，先从头到尾过一遍，按照ls[i]的三种可能，创造出来ls2数组
然后遍历ls2，找到sum[i]最大的值，输出就可以了。
输入输出部分
# 老规矩，先考虑输入输出
n = int(input())
ls = list(map(int, input().split()))
# 输入处理完毕
#
# 核心代码
#
print(maxn, end = "")
核心代码
#创建ls2数组
ls2 = [0 for i in range(max(ls) + 1)]
# 这里有个小问题
# 假设只有3 1 1 3，假设水在1这里，那应该是两个峰
# 3:1 1:0 1:0 3:1
# 但是，如果水在1的位置，淹没了，却不会减去
# 所以，应该把它变成 3:1 1:-1 3:1
# 因此需要去重。
# 遍历ls1，给ls2填数
ls_tmp = ls[:]
ls = []
ls.append(ls_tmp[0])
for i in range(len(ls_tmp)-1):
if ls_tmp[i] != ls_tmp[i+1]:
ls.append(ls_tmp[i+1])
#去重结束
#然后针对去重后的数组开始处理
for i in range(1,len(ls) - 1):
if ls[i] > ls[i-1] and ls[i] > ls[i+1]:
ls2[ ls[i] ] += 1
elif ls[i] < ls[i-1] and ls[i] < ls[i+1]:
ls2[ ls[i] ] -= 1
ls2[0] = 0
#给ls2的头和尾填数
if ls[0] > ls[1]:
ls2[ls[0]] += 1
n = len(ls)
if ls[n-1] > ls[n - 2]:
ls2[ls[n-1]] += 1
#这里需要注意的是，头尾只可能成为峰，不会成为谷。
#比如1 3 1，最少也是1。
maxn = 0
maxn_tmp = 0
for i in ls2[::-1]:
maxn_tmp += i
maxn = max(maxn, maxn_tmp)
汇总代码
n = int(input())
ls = list(map(int, input().split()))
ls2 = [0 for i in range(max(ls) + 1)]
ls_tmp = ls[:]
ls = []
ls.append(ls_tmp[0])
for i in range(len(ls_tmp)-1):
if ls_tmp[i] != ls_tmp[i+1]:
ls.append(ls_tmp[i+1])
for i in range(1,len(ls) - 1):
if ls[i] > ls[i-1] and ls[i] > ls[i+1]:
ls2[ ls[i] ] += 1
elif ls[i] < ls[i-1] and ls[i] < ls[i+1]:
ls2[ ls[i] ] -= 1
ls2[0] = 0
if ls[0] > ls[1]:
ls2[ls[0]] += 1
n = len(ls)
if ls[n-1] > ls[n - 2]:
ls2[ls[n-1]] += 1
maxn = 0
maxn_tmp = 0
for i in ls2[::-1]:
maxn_tmp += i
maxn = max(maxn, maxn_tmp)
print(maxn, end = "")
评测链接
【CSP 202109-2】首页 - 计算机软件能力认证考试系统