4007. 非零段划分
摘要
Title: 4007. 非零段划分
Tag: 差分
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
4007. 非零段划分
-
题意
-
思路
同 2014. 岛
题目问p以下变成0，有多少非零段划分
其实就可以转化为，当海平面在下降的过程中，有多少岛露出来 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24'''
Author: NEFU AB-IN
Date: 2022-03-16 19:23:35
FilePath: \ACM\Acwing\4007.py
LastEditTime: 2022-03-16 19:30:48
'''
from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
d = Counter()
nums = [0, *nums, 0] #差分时，别忘了处理边界
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
d[nums[i - 1]] += 1
d[nums[i]] -= 1
cnt, ans = 0, 0
for key in sorted(d.keys()):
cnt += d[key]
ans = max(ans, cnt)
print(ans)
