首页 > 代码库 > [USACO2005][POJ3044]City Skyline(贪心+单调栈)

[USACO2005][POJ3044]City Skyline(贪心+单调栈)

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

题意:以坐标的形式给出一张图,表示一些楼房的正视图,求出楼房的最少个数。

分析:和小学常做的立方体问题很像,很容易想到一个贪心方法,那就是尽量把矮的楼房放在高的楼房的前面,即连续的等高的一些"X"我们把它视为一座楼房。

        具体的做法可以维护一个Y坐标单增的栈,从左到右读入每个坐标,将Y坐标与栈顶坐标比较:

      若Y==栈顶坐标,那么接着读下面一个坐标

      若Y>栈顶坐标,那么把Y坐标加入栈成为新的栈顶

      若Y<栈顶坐标,那么弹出栈顶坐标,且ans+1表示前面一段以栈顶元素为共同高度的X作为一个楼房

总结:这题本身不是什么问题,不过此问题也可以看成给你一张图,让你用尽量少的矩形覆盖所有‘X‘且不能覆盖‘.‘,所以说类似的矩形覆盖问题也可以这么贪心。