2021-9-2非零段划分（前缀和最简解法）（c/c++实测满分）-创新互联

  区间原地划分时可以观察相邻元素之间的大小关系是否与划分有关。前缀和与差分实现单位时间内区间数值整体加1。（ccf-csp第二题真的很爱考前缀和。）

前缀和详解：

题目描述

A1,A2,⋯,An 是一个由 n 个自然数（非负整数）组成的数组。我们称其中 Ai,⋯,Aj 是一个非零段，当且仅当以下条件同时满足：

• 1≤i≤j≤n；
• 对于任意的整数 k，若 i≤k≤j，则 Ak>0；
• i=1 或 Ai−1=0；
• j=n 或 Aj+1=0。

下面展示了几个简单的例子：

• A=[3,1,2,0,0,2,0,4,5,0,2] 中的 4 个非零段依次为 [3,1,2]、[2]、[4,5] 和 [2]；
• A=[2,3,1,4,5] 仅有 1 个非零段；
• A=[0,0,0] 则不含非零段（即非零段个数为 0）。

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

输入格式

从标准输入读入数据。

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

输入的第二行包含 n 个用空格分隔的自然数 A1,A2,⋯,An。

输出格式

输出到标准输出。

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

样例1输入

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

Data

样例1输出

5

#includeusing namespace std;

const int N=1e5;
int a[N],b[N];
bool st[N];//该值是否曾经出现过

int main(){
	int n;
	cin>>n;
	int num=0;
	for(int i=0;ia[i-1]){//a[i-1]到a[i]-1段的p都能构成新的非零段
			b[a[i]]--;//处理差分数组以实现区间整体+1
			b[a[i-1]]++;
		}
	}

	int ans=0;
	for(int i=1;i<=M;i++){
		b[i]+=b[i-1];//求前缀和
		if(b[i]>ans) ans=b[i];//记录前缀和数组中的大值
	}
	  
	cout<

分析：

  当a[i]>a[i-1]时，只要p取到区间a[i-1]到a[i]-1中的值，都能构成一个新的非零段。这就是p与数组的关系，根据这个关系利用前缀和与差分实现单位时间内区间数值整体加1，将双重循环改进至单层，降低计算时间。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧