CCF CSP202109-2 non zero segment division

Title Description

A 1 , A 2 , ⋯ , A n A_1,A_2,⋯,A_n A1, A2,..., An is An array of n natural numbers (non negative integers). We call it A i , ⋯ , A j A_i,⋯,A_j Ai,..., Aj is a non-zero segment if and only if the following conditions are met at the same time:

• 1≤i≤j≤n；
• For any integer k, if i ≤ K ≤ j, then A k > 0 A_k>0 Ak​>0；
• i=1 or A i − 1 = 0 A_{i−1}=0 Ai−1​=0；
• j=n or A j + 1 = 0 A_{j+1}=0 Aj+1​=0.

Here are some simple examples:

• The four non-zero segments in A=[3,1,2,0,0,2,0,4,5,0,2] are [3,1,2], [2], [4,5] and [2];
• A=[2,3,1,4,5] has only one non-zero segment;
• A=[0,0,0] does not contain non-zero segments (that is, the number of non-zero segments is 0).

Now we can operate on array A as follows: select any positive integer P, and then change all numbers less than P in A to 0. Try to choose an appropriate p to maximize the number of non-zero segments in array A. If the number of non-zero segments contained in the input A has reached the maximum value, p=1 can be taken, that is, no modification will be made to A.

Input format

Read in data from standard input.

The first line of input contains a positive integer n.

The second line of input contains n natural numbers A1,A2,..., An separated by spaces.

Output format

Output to standard output.

Only one integer is output, indicating the maximum number of non-zero segments of array A after operation.

Example 1 input

11
3 1 2 0 0 2 0 4 5 0 2

Sample 1 output

5

Example 1 explanation

When p=2, A=[3,0,2,0,0,2,0,4,5,0,2], the five non-zero segments are [3], [2], [2], [4,5] and [2]; At this time, the number of non-zero segments reaches the maximum.

Example 2 Input

14
5 1 20 10 10 10 10 15 10 20 1 5 10 15

Sample 2 output

4

Example 2 explanation

When p=12, A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15], the four non-zero segments are [20], [15], [20] and [15]; At this time, the number of non-zero segments reaches the maximum.

Example 3 input

3
1 0 0

Sample 3 output

1

Example 3 explanation

When p=1, A=[1,0,0], there is only one non-zero segment [1], and the number of non-zero segments reaches the maximum.

Example 4 input

3
0 0 0

Sample output 4

0

Example 4 explanation

No matter what value p takes, A does not contain non-zero segments, so the number of non-zero segments is at most 0.

Subtask

70% of the test data meet n ≤ 1000;

All test data meet n ≤ 5 × 1 0 5 10^5 105, and each number in array A does not exceed 1 0 4 10^4 104.

Key point analysis

The first thought is to solve by violence, that is, try once from 0 to the maximum value of the sequence, and calculate the final results respectively. The specific code is as follows:

#include<stdio.h>
int n;
int a[500005];
int p;
int maxn=0;
int maxans = 0;
int f(int x);
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>maxn){
			maxn = a[i];
		}
	}
	if(maxn == 0 ){
		printf("0");
		return 0;
	}
	for(int i=1;i<=maxn;i++){
		int tmp = f(i);
		if(tmp>maxans)maxans=tmp;
	}	
	printf("%d",maxans);
}
int f(int x){
	int pre = 0;
	int ans = 0;
	for(int i=0;i<=n;i++)
	{
		if(pre==0 && a[i]>=x){
			ans++;
			pre = 1;
		}
		else if(pre == 1 && a[i]<x){
			pre = 0;
		}
	}
	return ans;
}

As a result, 70% of the data can be exceeded, and the error is reported, and the operation times out.

So, I thought, I can scan the sequence, calculate the result, and then take the maximum value. Since the maximum value is less than 10000, a 10005 size array b can be created to store the corresponding results when p is the value respectively. As long as a rising interval is encountered, the results of the corresponding interval will be added by one. For example, if the subsequence [2,5] is encountered, the corresponding b[3], b[4] and b[5] are added by one respectively.

The specific codes are as follows:

#include<bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int b[10005];
int maxn=0;
int maxans = 0;
int main()
{
	memset(b,0,sizeof(b));
	scanf("%d",&n);
	scanf("%d",&a[1]);
	for(int i=1;i<=a[1];i++){
		b[i]++;
	}
	maxn = max(a[1],0);
	for(int i=2;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>a[i-1]){
			for(int j=a[i-1]+1;j<=a[i];j++){
				b[j]++;
			}
		}
		maxn=max(a[i],maxn);
	}
	for(int i=1;i<=maxn;i++){
		maxans=max(b[i],maxans);
	}
	printf("%d",maxans);
}