题解 SP15620 【POSTERIN - Postering】

显而易见，建筑的宽度对答案完全没有影响。
并且，给每一个建筑分别贴一张海报一定是一种方案。
考虑什么情况下可以减少需要的海报数量。

可以发现，当有两个建筑物高度相等，且中间的所有建筑都高于它，则可以少用一张海报。

直接使用单调栈即可，复杂度$O(n)$。

#include<iostream>
using namespace std;
int stk[250005],a[250005];
int main(){
	int n,top=-1,ljt,ans;
	cin>>n;
	ans=n;
	for(int i=1;i<=n;i++)cin>>ljt>>a[i];
	for(int i=1;i<=n;i++){
		while(top>=0&&a[stk[top]]>a[i])top--;//单调栈向前推
		if(top>=0&&a[stk[top]]==a[i]){//统计答案
			top--;
			ans--;
		}
		stk[++top]=i;//插入单调栈
	}
	cout<<ans; 
	return 0;
}