UVa 105 The Skyline Problem （想法题）

UVa 105 The Skyline Problem （想法题）2014-10-04 csdn synapse7

105 - The Skyline Problem

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=41

这题有个很巧的思路：离散化。

什么意思呢？既然每栋大楼的高和左右边界都是整数，那么不妨把线段用一个个整点表示。既然最后只求一个轮廓，那么对每个横坐标，就记录纵坐标（高度）最大的点。最后从左到右扫描一遍，当高度发生变化时就输出。

完整代码：

/*0.039s*/#include<bits/stdc++.h>using namespace std;const int maxn = 10005;int hi[maxn];int main（）{int i, l, h, r, maxr = 0;while （~scanf（"%d%d%d", &l, &h, &r））{for （i = l; i < r; i++）hi[i] = max（hi[i], h）; ///注意右端点处不记录高度maxr = max（maxr, r）;}for （i = 1; i < maxr; ++i）if （hi[i] ！= hi[i - 1]）printf（"%d %d ", i, hi[i]）;printf（"%d 0
", maxr）;return 0;}

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45438.htm