[CSP-J 2022 山东] 植树节(Arbor Day) 题解

思路分析

树苗编号范围为 $[0, 10^6]$（注意下标从 $0$ 开始！）。开差分数组 diff[0..1000001]，每个区间 $[a_i, b_i]$ 执行 diff[a_i]++, diff[b_i + 1]--，最后对 $0 \sim 10^6$ 求前缀和并取最大值即可。时间复杂度 $O(n + V)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

const int MX = 1000005;
int diffArr[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        diffArr[a]++;
        diffArr[b + 1]--;
    }
    int cur = 0, ans = 0;
    for (int i = 0; i <= 1000000; ++i)
    {
        cur += diffArr[i];
        ans = max(ans, cur);
    }
    cout << ans << "\n";
    return 0;
}