UVa 105 The Skyline Problem (想法题)

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 0n", maxr);
return 0;
}

最后

以上就是故意冰淇淋为你收集整理的UVa 105 The Skyline Problem (想法题)的全部内容，希望文章能够帮你解决UVa 105 The Skyline Problem (想法题)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。