UVa 105 The Skyline Problem (想法题) - c++编程基础

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

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

完整代码：

/*0.039s*/  
  
#include  
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\n", maxr);  
    return 0;  
}