题解：SP3921 BYTESE2 - The Great Ball

· · 题解

题目传送门

闲话：我绑定了 SPOJ 但是在洛谷还是交不了题，于是我在 SPOJ 里面提交过的。

题意

有 t 组数据，每组数据中有 n 个人进出房间的记录，求同一时间在房间的人数的最大值。

思路

我们把所有时间点看作一条时间轴，每个人进出就相当于进入时间到离开时间这一段的房间人数加一。暴力肯定会慢到爆炸，于是我们可以想到用差分。顾名思义，就是第 i 项存放第 i 项与第 i-1 项的差，如果要得到原数，就从第一项加到原数的前一项。那么这时候区间修改就只用 O(1) 的时间复杂度了，设进入时间为 l，离开时间为 r，那么只需要将 d_l+1，再将 d_r-1 就行了（d 为差分数组）。细节看代码。

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, a, b, sum, ans, l, r, d[10000010];
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        a = 1e7 + 5, b = sum = ans = 0, memset(d, 0, sizeof(d));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &l, &r);
            d[l]++, d[r]--, a = min(a, l), b = max(b, r);
        }
        for (int i = a; i <= b; i++)
            sum += d[i], ans = max(ans, sum);
        printf("%d\n", ans);
    }
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门