202109-2 非零段划分--C++

#include <iostream>
#include <bits/stdc++.h>

using namespace std;



int A[500001];


int FindSum(int A[],int p,int n)
{
	for(int i=1;i<=n;i++)//所有小于p的都变0 
	{
		if(A[i]<p) A[i]=0;
	}
	
	int sum=0;
	for(int i=1;i<=n;i++)
	 	{
	 		if(A[i]!=0&&A[i+1]==0) sum++;
		 }
		 
		 return sum;
	
}

int main()
{
	
	int n;//n个数
	
	
	 int Mostp=0;
	 
	 cin>>n;
	 
	 int sum=0;//记录不做任何操作时的总的非0段数 
	 
	 cin>>A[1];
	for(int i=2;i<=n;i++)
	{
		cin>>A[i];
		if(A[i]>Mostp) Mostp=A[i];
		if(A[i-1]==0&&A[i]!=0) sum++;
	 }
	 
	 if(A[n]!=0) sum++;
	 
	
	 for(int p=2;p<=Mostp;p++)
	 {
	 	if(FindSum(A,p,n)>sum) sum=FindSum(A,p,n);
	 	
	  } 
	  
	  cout<<sum;

	return 0;
}

暴力算法：70分

差分法+前缀和：

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

const int N = 500000;
const int M = 10000;
int a[N+2], d[M+1];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    a[0] = a[n+1] = 0;

    // unique 去除相邻重复的元素，并把他们移动到末尾
    // n 为相邻不重复时的数组长度，从0到n，不包括n
    n = unique(a, a+n+2)-a;//unique,去除相邻的重复元素，返回的是去除之后的元素个数 

    memset(d, 0, sizeof d);//对较大的结构体或数组进行清零操作的一种最快方法

    for (int i = 1; i < n-1; i++){//当p=i时有几个凸点 
        if (a[i-1] < a[i] && a[i] > a[i+1]){
            d[a[i]]++;
        }else if (a[i-1]>a[i] && a[i]<a[i+1]){
            d[a[i]]--;
        }
    }

    int ans = 0, sum = 0; //差分后缀和即为答案
    for (int i = M; i >= 1; i--){
        sum += d[i], ans = max(ans, sum);
    }

    cout << ans << endl;

    return 0;
}

CCF 202109-2 非零段划分（C++）差分法 - 白缺 - 博客园 (cnblogs.com)