[USACO2005][POJ3044]City Skyline(貪心+單調棧）

題目：http://poj.org/problem?id=3044

題意：以坐标的形式給出一張圖，表示一些樓房的正視圖，求出樓房的最少個數。

分析：和國小常做的立方體問題很像，很容易想到一個貪心方法，那就是盡量把矮的樓房放在高的樓房的前面，即連續的等高的一些"X"我們把它視為一座樓房。

        具體的做法可以維護一個Y坐标單增的棧，從左到右讀入每個坐标，将Y坐标與棧頂坐标比較：

　　　　　　若Y==棧頂坐标，那麼接着讀下面一個坐标

　　　　　　若Y>棧頂坐标，那麼把Y坐标加入棧成為新的棧頂

　　　　　　若Y<棧頂坐标，那麼彈出棧頂坐标，且ans+1表示前面一段以棧頂元素為共同高度的X作為一個樓房

總結：這題本身不是什麼問題，不過此問題也可以看成給你一張圖，讓你用盡量少的矩形覆寫所有‘X‘且不能覆寫‘.‘,是以說類似的矩形覆寫問題也可以這麼貪心。