题解 | City Horizon-牛客假日团队赛3F题

F-City Horizon_牛客假日团队赛3

https://ac.nowcoder.com/acm/contest/945/F

题目描述

Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.
The entire horizon is represented by a number line with $N (1 ≤ N ≤ 40,000)$ buildings. Building i's silhouette has a base that spans locations Ai through Bi along the horizon $(1 ≤ A_i < B_i ≤ 1,000,000,000)$ and has height $H_i (1 ≤ H_i ≤ 1,000,000,000)$ . Determine the area, in square units, of the aggregate silhouette formed by all N buildings.

输入描述:

Line 1: A single integer: $N$

Lines 2..N+1: Input line i+1 describes building i with three space-separated integers: $A_i, B_i,$ and $H_i$

输出描述:

Line 1: The total area, in square units, of the silhouettes formed by all N buildings

示例1

输入

4
2 5 1
9 10 4
6 8 2
4 6 3

输出

16

说明

The first building overlaps with the fourth building for an area of 1 square unit, so the total area is just $31 + 14 + 22 + 23 - 1 = 16.$

解答

其实这题也可以不用线段树，比较”标准”的做法是线段树扫描线求矩形面积并，但这题是简化过了的。

（建议大家学习下线段树扫描线，百度即可，经典例题HDU1542)

简化过是因为在纵坐标上是从0开始的，那么维护一个高度就可以了。

然后就发现我们需要一个数据结构，它应该支持插入，删除，求最大值，于是我们就想到树之类的东西，总之时间复杂度要都是 $O(log n)$ 。

因为我比较懒，就直接用了STL里面的multiset维护高度。（考虑到可能有重复的高度）

然后把一个矩形拆成两条线段，按横坐标排序，从左到右扫描一遍，遇到左边就把这个高度插入集合，遇到右边就把它踢出去，答案每次加上最大高度乘上两个节点间的 $x$ 距离。

注意答案要开long long!!做加法的时候也要转一下，要不就是蜜汁60分了。

注意开节点数组要开 $2n$ 。

以下是代码，仅供参考。

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define maxn 80005
typedef multiset<int, greater<int> > msi;
typedef long long LL;
struct seg {
    int x, h, d;
    seg() {}
    seg(int a, int b, int c) : x(a), h(b), d(c) {}
    bool operator < (const seg& rhs) const
    {
        return x < rhs.x;
    }
} s[maxn];
int main()
{
    int n, a, b, k, i, p = 0;
    LL ans = 0;
    msi h;
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d%d%d", &a, &b, &k);
        s[p++] = seg(a, k, 1);
        s[p++] = seg(b, k, 0);
    }
    sort(s, s + p);
    h.insert(0);
    for (i = 0; i < p - 1; ++i) {
        if (s[i].d)
            h.insert(s[i].h);
        else {
            msi::iterator it = h.find(s[i].h);
            h.erase(it);
        }
        ans += LL(*h.begin()) * (s[i + 1].x - s[i].x);
    }
    printf("%lld\n", ans);
}

来源：__hao__