首页 > 代码库 > BZOJ 1113: [Poi2008]海报PLA
BZOJ 1113: [Poi2008]海报PLA
题目
1113: [Poi2008]海报PLA
Time Limit: 10 Sec Memory Limit: 162 MBDescription
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
题解
这道题目，我们可以像一旦出现高度一样的就可以用同一张海报盖掉，但是两张海报之中的海报就只能单独再贴了。基于这个思路，我们可以写一个单调栈。
代码
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 using namespace std; 4 int t,x,n,s[250001],top,ans; 5 int main(){ 6 scanf("%d",&n); 7 for(int i=1;i<=n;i++){ 8 scanf("%d%d",&t,&x); 9 while(x<=s[top]){10 if(x==s[top])ans++;11 top--;12 }13 s[++top]=x;14 }15 printf("%d",n-ans);16 return 0;17 }
BZOJ 1113: [Poi2008]海报PLA
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。