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
```

```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
```

```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.

```3
1 0 0
```

```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.

```3
0 0 0
```

```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.

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);
}
```

Keywords: CCF

Added by think-digitally on Mon, 21 Feb 2022 14:41:25 +0200