想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全
| 试题编号： | 202109-2 |
| 试题名称： | 非零段划分 |
| 时间限制： | 1.0s |
| 内存限制： | 512.0MB |
| 问题描述： | 题目描述A1,A2,⋯,An 是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段，当且仅当以下条件同时满足：
下面展示了几个简单的例子：
现在我们可以对数组 A 进行如下操作：任选一个正整数 p，然后将 A 中所有小于 p 的数都变为 0。试选取一个合适的 p，使得数组 A 中的非零段个数达到最大。若输入的 A 所含非零段数已达最大值，可取 p=1，即不对 A 做任何修改。 输入格式从标准输入读入数据。 输入的第一行包含一个正整数 n。 输入的第二行包含 n 个用空格分隔的自然数 A1,A2,⋯,An。 输出格式输出到标准输出。 仅输出一个整数，表示对数组 A 进行操作后，其非零段个数能达到的最大值。 样例1输入11 样例1输出5 样例1解释p=2 时，A=[3,0,2,0,0,2,0,4,5,0,2]，5 个非零段依次为 [3]、[2]、[2]、[4,5] 和 [2]；此时非零段个数达到最大。 样例2输入14 样例2输出4 样例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 样例3输出1 样例3解释p=1 时，A=[1,0,0]，此时仅有 1 个非零段 [1]，非零段个数达到最大。 样例4输入3 样例4输出0 样例4解释无论 p 取何值，A 都不含有非零段，故非零段个数至多为 0。 子任务70% 的测试数据满足 n≤1000； 全部的测试数据满足 n≤5×105，且数组 A 中的每一个数均不超过 104。 |
真题来源：非零段划分
感兴趣的同学可以进去进行练习提交
满分题解：
n = int(input())
nums = [0]+list(map(int,input().split()))+[0]
point = {}
max_ = 0
for id, value in enumerate(nums):
if not value:
continue
max_ = max(max_, value)
if value not in point:
point[value] = [id]
else:
point[value].append(id)
island = [0]*(n+2)
temp = 0
top = 0
for data in range(max_, 0, -1):
if data not in point:
continue
for i in point[data]:
if island[i-1] == 0 and island[i+1] == 0:
top += 1
elif island[i-1] == 1 and island[i+1] == 1:
top -= 1
island[i] = 1
temp = max(top,temp)
print(temp)
解题思路：
本题主要利用了一种水平面岛屿的思想，找出数值中的最大值，作为最高的水平面，不断下降水面，记录每次下降之后的岛屿的数量，进行比较选出最多的岛屿数量。
运行结果：
ccf-csp练习专栏
https://blog.csdn.net/weixin_53919192/category_11828479.html?spm=1001.2014.3001.5482https://blog.csdn.net/weixin_53919192/category_11828479.html?spm=1001.2014.3001.5482
