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

前言

致敬传奇入门组有紫。

正言

首先，要求浇水次数最多的树，每隔志愿者会给第

a_i \sim b_i

棵树之间贡献一次浇水次数。

那么很容易发现，这就是一个区间加，并且没有修改操作，那么这就是一个板子的差分。

但是，我们要注意，

a_i,b_i

可以为

0

啊。而差分数组转回正常数组是要用到前缀和，这里会越界。

那我们怎么办呢？

这里给出一种解决方法，那就是将操作的左右端点加

1

，让操作从

1

开始，这样就不会越界了，同时，要注意最后求答案的时候要到

10^6+1

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,a[N],b[N],maxv;
void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        insert(l+1,r+1,1);
    }
    for(int i=1;i<=1000001;i++){
        b[i]+=b[i-1];
        maxv=max(maxv,b[i]);
    }
    cout<<maxv<<endl;
    return 0;
}

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

文章操作

前言

正言

代码

相关推荐

评论

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