自动搬运

查看原文

来自洛谷，原作者为

	2011hym 暴力占据大脑，打表代替思考 | 寒鸦栖枯地，拿分靠暴力 | 空山不见人，爆0就红温

搬运于2025-08-24 23:10:49，当前版本为作者最后更新于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 = 0; i < n; i++) {
        cin >> a >> b;
        diff[a]++;
        if (b + 1 <= 1000010) diff[b + 1]--;//先进行差分
    }
    for (int i = 0; i <= 1000000; i++) {
        c += diff[i];
        if (c > sum) sum = c;//再进行前缀和
    }
    cout << sum;
    return 0;
}

一道橙题就这么被秒了。

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