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

2011hym · 2025-03-05 18:31:24 · 题解

题目分析

一道比较水的差分题目。

本题的核心问题是有一排编号从 0 开始的树苗，n 个志愿者会分别给一个区间内的树苗浇水，需要找出浇水次数最多的树苗的浇水次数。

思路分析

本题可以使用差分的思想来解决。差分是一种对区间进行修改的高效方法，通过记录区间端点的变化，最后再通过前缀和还原出每个位置的实际值。

先进行读入，再将每次差分的数据求出。

• 通过前缀和的方式还原每个位置的实际浇水次数。c += diff[i] 表示当前位置的浇水次数等于前一个位置的浇水次数加上当前位置的变化量。
• 在计算过程中，不断更新 sum 的值，确保 sum 始终记录着浇水最多的树苗的浇水次数。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
int diff[1000010],n,a,b,sum,c;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){//差分。
        cin>>a>>b;
        diff[a+1]++;//这里注意，这里我所用的下标与题目不一样。
        diff[b+2]--;//所以下标是 a+1 和 b+2。
    }
    for(int i=1;i<=1000000;i++){//前缀和。
        c+=diff[i];
        sum=max(sum,c);
    }
    cout<<sum;
    return 0;
}

一道橙题就这么被秒了。

upd：2025.7.17 感谢三位好心人指出错误。

upd：2025.10.3 震惊于以前自己的~米田共山~代码并且进行了修改。