题解 | #植树节#

题目链接

题目描述

一排从 0 开始无限延伸的树苗，有 $n$ 名志愿者。第 $i$ 名志愿者会对闭区间 $[l_i, r_i]$ 内的每一棵树苗浇一次水。求所有志愿者完成后，被浇水次数最多的树苗被浇了多少次水。

解题思路

本题要求的是多个区间覆盖后，单个点的最大覆盖次数。

我们可以想象一个记录每棵树被浇水次数的数组 counts。每名志愿者对区间 $[l, r]$ 进行浇水，就相当于将 counts 数组在 $[l, r]$ 区间内的所有值都加 1。在所有志愿者操作完后，我们需要求 counts 数组中的最大值。

如果对每个志愿者的区间都进行一次遍历更新，当区间很大、志愿者很多时，总时间复杂度会非常高，导致超时。

这是一个典型的区间批量修改问题，可以使用差分数组来高效解决。

差分数组的应用 差分数组可以将区间修改操作转化为两次单点修改。

我们创建一个差分数组 diff，diff[i] 记录了 counts[i] 相对于 counts[i-1] 的变化量。
当一个区间 $[l, r]$ 需要全部加 1 时，我们只需要：
- diff[l] 增加 1。这表示从 $l$ 点开始，浇水次数相对于前一个点增加了 1。这个效应会通过前缀和一直传递下去。
- diff[r+1] 减少 1。这表示在 $r+1$ 点，之前从 $l$ 点开始的增加效应被抵消了。这样就保证了增加操作只影响到 $[l, r]$ 区间。
对所有 $n$ 个区间执行上述的两次单点修改后，差分数组 diff 就记录了所有的变化信息。
最后，我们对差分数组 diff 求前缀和，就可以还原出每个点最终的浇水次数。在求前缀和的过程中，我们同时记录遇到的最大值，即为题目所求的答案。

算法步骤：

根据题目给出的坐标范围（最大到 $10^6$ ），创建一个足够大的差分数组 diff（例如，大小为 $10^6+2$ ），并初始化为 0。
读入 $n$ 个区间 $[l, r]$ 。对于每个区间，执行 diff[l]++ 和 diff[r+1]--。
遍历差分数组 diff，计算前缀和。维护一个当前浇水次数 current_watering 和一个最大浇水次数 max_watering。
从左到右遍历 diff 数组，current_watering 累加上 diff[i] 的值，然后用 current_watering 更新 max_watering。
遍历结束后，max_watering 就是最终的答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_COORD = 1000001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 差分数组，大小比最大坐标多2以防 r+1 越界
    vector<int> diff(MAX_COORD + 2, 0);
    int max_r = 0; // 记录最右边的坐标，减少不必要的遍历

    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
        max_r = max(max_r, r);
    }

    long long max_watering = 0;
    long long current_watering = 0;

    // 遍历到最右边的坐标即可
    for (int i = 0; i <= max_r; ++i) {
        current_watering += diff[i];
        max_watering = max(max_watering, current_watering);
    }

    cout << max_watering << "\n";

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        final int MAX_COORD = 1000001;
        int[] diff = new int[MAX_COORD + 2];
        int maxR = 0;

        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            diff[l]++;
            diff[r + 1]--;
            maxR = Math.max(maxR, r);
        }

        long maxWatering = 0;
        long currentWatering = 0;

        for (int i = 0; i <= maxR; i++) {
            currentWatering += diff[i];
            maxWatering = Math.max(maxWatering, currentWatering);
        }

        System.out.println(maxWatering);
    }
}

import sys

def main():
    n = int(sys.stdin.readline())
    
    # 坐标范围较大，需要合适的数组大小
    MAX_COORD = 1000001
    diff = [0] * (MAX_COORD + 2)
    max_r = 0

    for _ in range(n):
        l, r = map(int, sys.stdin.readline().split())
        diff[l] += 1
        diff[r + 1] -= 1
        if r > max_r:
            max_r = r
            
    max_watering = 0
    current_watering = 0
    
    # 遍历到最右边的坐标即可
    for i in range(max_r + 1):
        current_watering += diff[i]
        if current_watering > max_watering:
            max_watering = current_watering
            
    print(max_watering)

if __name__ == "__main__":
    main()

算法及复杂度

算法：差分数组
时间复杂度： $O(N + C)$ ，其中 $N$ 是志愿者数量， $C$ 是最大的区间端点坐标。 $O(N)$ 用于处理所有区间的输入并更新差分数组， $O(C)$ 用于遍历差分数组以计算最终结果。
空间复杂度： $O(C)$ ，用于存储差分数组。