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

Wide_Master · 2025-03-05 19:53:29 · 题解

前言

致敬传奇入门组有紫。

正言

首先，要求浇水次数最多的树，每隔志愿者会给第 a_i \sim b_i 棵树之间贡献一次浇水次数。

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

但是，我们要注意，a_i,b_i 可以为 0 啊。而差分数组转回正常数组是要用到前缀和，这里会越界。

那我们怎么办呢？

这里给出一种解决方法，那就是将操作的左右端点加 1，让操作从 1 开始，这样就不会越界了，同时，要注意最后求答案的时候要到 10^6+1。

代码

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