N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.
N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.
第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering
最少数量的海报数.
题解：先假设一共盖住一个矩形需要一张海报，那么需要n张海报。再思考什么情况可以减少海报的数量。
如果两个房子登高，两个房子中间的房子都要高于这两个房子，那么显然可以用一张海报完全遮盖住这两
栋房子，这个过程我们可以用单调栈维护单调性，在弹栈操作时实现这一思想。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 6 using namespace std; 7 8 int s[250005],top,n; 9 10 int main() 11 { 12 scanf("%d",&n); 13 int w,h,ans=n; 14 for(int i=1;i<=n;i++) 15 { 16 scanf("%d%d",&w,&h); 17 while(s[top]>=h) 18 { 19 if(s[top]>h) top--; 20 else top--,ans--; 21 } 22 s[++top]=h; 23 } 24 printf("%d",ans); 25 return 0; 26 }
原文：https://www.cnblogs.com/Hoyoak/p/11399182.html