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

· · 题解

题意

给定了一个全部为 0 的序列，每次对一个区间范围内的数加 1 ，求区间内最大的数

思路

题目要求对一个区间内的数加上 1 ，那么直接套差分就可以了。

不过要注意序列从 0 开始，所以可以将整个序列都向后挪 1就不会在计算原数组时越界了。

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

code

#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;
}