Description

N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

Input

第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering

Output

最少数量的海报数.

 

题解：先假设一共盖住一个矩形需要一张海报，那么需要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 }