csp 202109-2 非零段划分

csp 202109-2 非零段划分

问题描述
试题编号： 202109-2
试题名称： 非零段划分
时间限制： 1.0s
内存限制： 512.0MB
问题描述：
题目描述
是一个由 个自然数（非负整数）组成的数组。我们称其中 是一个非零段，当且仅当以下条件同时满足：

；
对于任意的整数 ，若 ，则 ；
或 ；
或 。
下面展示了几个简单的例子：

中的 个非零段依次为 、、 和 ；
仅有 个非零段；
则不含非零段（即非零段个数为 ）。
现在我们可以对数组 进行如下操作：任选一个正整数 ，然后将 中所有小于 的数都变为 。试选取一个合适的 ，使得数组 中的非零段个数达到最大。若输入的 所含非零段数已达最大值，可取 ，即不对 做任何修改。

输入格式
从标准输入读入数据。

输入的第一行包含一个正整数 。

输入的第二行包含 个用空格分隔的自然数 。

输出格式
输出到标准输出。

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

样例1输入
11
3 1 2 0 0 2 0 4 5 0 2
Data
样例1输出
5
Data
样例1解释
时，， 个非零段依次为 、、、 和 ；此时非零段个数达到最大。

样例2输入
14
5 1 20 10 10 10 10 15 10 20 1 5 10 15
Data
样例2输出
4
Data
样例2解释
时，， 个非零段依次为 、、 和 ；此时非零段个数达到最大。

样例3输入
3
1 0 0
Data
样例3输出
1
Data
样例3解释
时，，此时仅有 个非零段 ，非零段个数达到最大。

样例4输入
3
0 0 0
Data
样例4输出
0
Data
样例4解释
无论 取何值， 都不含有非零段，故非零段个数至多为 。

子任务
的测试数据满足 ；

全部的测试数据满足 ，且数组 中的每一个数均不超过 。

解题思路

差分数组，可以理解成岛屿问题，让p从最大开始，逐渐下降（海平面下降），遇到山峰+1，遇到山谷-1.

代码

#include 
#include 
#include 

using namespace std;
int cent[10010] = {0};

int main(){
//输入
	int n;
	cin >> n;
	vector<int> a;
	//头尾添加0，简化边界处理
	a.push_back(0);
	int temp; 
	for(int i = 1;i<=n;i++){
		cin>>temp;
		if(temp!=a.back()){
			a.push_back(temp);
		}
	}
	a.push_back(0);
	//寻找山峰山谷
	for(int i=1;i<a.size()-1;i++){
		if(a[i]>a[i-1]&&a[i]>a[i+1]){
			cent[a[i]]++;
		}
		if(a[i]<a[i-1]&&a[i]<a[i+1]){
			cent[a[i]]--;
		}
	}
	
	int maxi = 0;
	temp = 0;
	
	for(int i = 10000;i>0;i--){
		temp += cent[i];
		maxi = max(temp,maxi);
	}
	cout<<maxi<<endl;
	return 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42