首页 > 代码库 > [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‘且不能覆盖‘.‘,所以说类似的矩形覆盖问题也可以这么贪心。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。