好久没用过单调栈了 练练手
最多贴n块海报
我们发现能省海报的情况 当且仅当有两个矩形 他们高度一样 而中间夹着的矩形都比且他们高
维护高的单调栈 每加入一个矩形 判断它左边第一个小于等于它高度的矩形的高度是否等于它的高度
#include<bits/stdc++.h> using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,sta[250005],top; int main() { read(n); int ans=n; for(int i=1,x,y;i<=n;i++) { read(x); read(y); while(top&&sta[top]>y) top--; if(sta[top]==y) ans--; sta[++top]=y; } cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9848115.html
