首页 > 代码库 > bzoj 1113 海报pla
bzoj 1113 海报pla
Description
N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.
Input
第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering
Output
最少数量的海报数.
Sample Input
5
1 2
1 3
2 2
2 5
1 4
1 2
1 3
2 2
2 5
1 4
Sample Output
4
【解析】
单调增栈。
显然贴海报只与矩形的高有关。发现当两个矩形高相同并且这两个矩形之间的矩形的高度都比他们大时可以用一张海报。
否则增加一张海报。
我们维护一个单调增栈，那么栈中的每一个元素左边的第一个元素就是第一个小于或者是等于当前元素的元素。判断是否相等，不相等就必须为当前
矩形增加一个海报。
【code】
#include<iostream> #include<cstdio> using namespace std; #define N 250005 int n,top,ans,l,h; int sta[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&l,&h); while(top&&sta[top]>h)top--; sta[++top]=h; if(sta[top-1]!=sta[top])ans++; } printf("%d",ans); return 0; }
bzoj 1113 海报pla
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。