题目链接
单调栈（维护单调递增）。
矩形的宽度与答案无关，我们只需处理矩形的高度。
code
#include<bits/stdc++.h> using namespace std; int h[50005],x,n,w; int ans,s[50005],top; inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0'; c=getchar();} return x*f; } int main() { freopen("skyline.in","r",stdin); freopen("skyline.out","w",stdout); n=read(); w=read(); for(int i=1;i<=n;i++) x=read(),h[i]=read(); ans=n; for(int i=1;i<=n;i++ ){ while(s[top]>h[i]&&top) top--; if(s[top]==h[i]) ans--; else s[++top]=h[i]; } printf("%d",ans); return 0; } #inc
