P1496 火烧赤壁 题解

· · 题解

题解区没有用 map 实现离散化的，我来补一发。

考虑使用差分统计出着火的区间，但由于 -2^{31}\le a\le b\le2^{31}，所以需要用 map，就像这样：

map<int, int> d; //差分
++d[a];
--d[b]; //注意左闭右开

模拟样例，可得知 d 为：

键 -1 1 2 5 9 11
值 1 -1 1 1 -1 -1

最后结果统计的是 长度之和，所以要用 last 维护上一个区间的右端点以便求和。

最终代码：

#include <cstdio>
#include <map>

using namespace std;

int n, a, b;
int ans; //答案
int sum; //前缀和
int last;
map<int, int> d; //差分

int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &a, &b);
        ++d[a];
        --d[b]; //注意左闭右开
    }
    for (register auto it: d) { //遍历 map
        if (sum > 0) //若着火了（右端点）
            ans += it.first - last; //求出着火区间长度
        sum += it.second; //求前缀和
        last = it.first; //更新右端点
    }
    printf("%d", ans);
    return 0;
}

AC 链接