[python和CSP的姻缘]202109-2 非零段划分

思路

这个题看的时间超级长，主要是不太理解差分，也看不出来怎么联系到那里的
这个题解法很多，快考试了也就不研究那么多解法了，单研究个比较常考的差分法好啦

这里可以理解成找到一个水平线来上下分割
当p值足够大时，所有陆地都被海水淹没了，只有0个岛屿；p下降即海平面下降时，山峰逐渐凸显，每多一个岛屿露出水面，就多一个岛屿，没当一个凹谷出现，两边的岛屿相连就会少一个岛屿

• 这就可以用两次遍历：
  首先需要设置一个差分数组，index是山的高度即数组A里的数值，对应的值是海平面到这里时岛屿变化的数量
  • 第一次遍历：
    遍历原来读入的数据A，看是山峰还是山谷，山峰的话则在差分数组对应的值里+1；山谷则-1
  • 第二次遍历：
    倒着遍历差分数组，即海平面从高到低下降，累加看后缀和的最大值

代码

n = int(input())
A = list(map(int,input().split()))+[0]
A = [0] + [A[i] for i in range(n) if A[i]!=A[i+1]]+[0]
max_line = max(A)
diff = [0] * ((max_line+1)*2)   # 差分数组

for i in range(1,len(A)-1):
    if A[i-1]<A[i] and A[i+1]<A[i]:     # 山峰
        diff[A[i]] += 1     # 海平面到这个位置的山峰
    elif A[i-1]>A[i] and A[i+1]>A[i]:   # 山谷
        diff[A[i]] -= 1

max_diff = 0
for i in range(max_line,-1,-1):
    diff[i] += diff[i+1]
    max_diff = max(max_diff,diff[i])
print(max_diff)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18