题意

给定了一个全部为

0

的序列，每次对一个区间范围内的数加

1

，求区间内最大的数

思路

题目要求对一个区间内的数加上

1

，那么直接套差分就可以了。

不过要注意序列从

0

开始，所以可以将整个序列都向后挪

1

就不会在计算原数组时越界了。

并且还要注意题目并没有给出序列的长度，所以还要计算出最大的

b

来。

code

CPP

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,r;
int a[N],b[N],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x++,y++;  //将整个序列整体向后挪1
		b[x]++;b[y+1]--;  //差分
		r=max(r,y); //计算序列的长度
	}
	for(int i=1;i<=r;i++)
	{
		a[i]=a[i-1]+b[i];  //求出原数组
		ans=max(ans,a[i]);  //统计最大值
	}
	cout<<ans<<endl;
	return 0;
}

题解：P11853 [CSP-J2022 山东] 植树节

文章操作

题意

思路

code

相关推荐

评论

题解：P11853 [CSP-J2022 山东] 植树节