UVa 105 – The Skyline Problem（利用判断，在于想法）

题目来源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41

解题思路：

当看到题目时,仔细想想感觉用暴力方法挺复杂的.需要判断建筑是否重叠,找到高度的变化位置,找出对应的左值,找出对应的右值.能这么想就很接近我要讲的解题方法了.

我们是需要找到高度转折点,找到最大的右值.

高度转折点的寻找：判断高度是否和前面的高度不同.但是这个建筑物是二维图形,如何去找建筑的分界点有些很复杂.由于题目中所给的限定,我们可以把建筑分成不连续的正整数点所围成.这样利用for循环,每次横坐标的值加1.直到高度变化之后,说明这里需要输出.(前提是我们要把这些不连续的正整数横坐标确定之后找出他们的最大的高度,利用for循环,横坐标每次加1,不断修改某一点的高度值)

下面给出代码：

1 #include<bits/stdc++.h>
 2 #define MAX 10010
 3 
 4 using namespace std;
 5 
 6 int height[MAX];
 7 
 8 int main()
 9 {
10     int i,l,h,r,max_right=-1;
11     while (~scanf("%d%d%d", &l, &h, &r))
12     {
13         memset(height,0,sizeof(height));
14         for (i=l; i<r; i++)
15             height[i]=max(height[i], h); //注意右端点处不记录高度
16         max_right=max(max_right,r);
17     }
18     for (i=1; i<max_right; i++)
19         if (height[i]!=height[i-1])
20             printf("%d %d ",i,height[i]);
21     printf("%d 0\n", max_right);
22     return 0;
23 }

推荐博客链接：

http://www.cnblogs.com/devymex/archive/2010/08/07/1794533.html

原文链接: https://www.cnblogs.com/zpfbuaa/p/5041502.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍