学步园

题目连接:

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

题解:

类似于数据结构中并查集

AC CODE

#include <iostream>
#include <cstdio>
using namespace std;

int sky[10001] = {0};
int Left = 10001,Right = 0;

int main()
{
   // freopen("input.txt","r",stdin);

    int L,H,R;

    while (cin >> L >> H >> R)
    {
        //构造sky[L...R]区间内的轮廓
        for (int i = L; i != R; i++)
            sky[i] = sky[i] > H ? sky[i] : H;
        
        Left = Left < L ? Left : L;
        Right = Right > R ? Right : R;
    }

    while (Left < Right)
    {
        // 输出其X下标值
        cout << Left << ' ';
        // 找出不相等的高度值
        while (sky[Left] == sky[Left+1])
            Left++;
        cout << sky[Left] << ' ';
        Left++;
    }
    cout << Right << " " << 0 << endl;
}