一道思维水题

首先，清楚题目理解障碍。

理解

题目中的海报是可以这样贴的：

注意：画黑色框的是建筑物，红色框的是海报。

从这可以看出海报可以将 $n$ 个建筑物的侧面连起来。

题目思路

我们可以显然看出贴满这 $n$ 个建筑物的侧面可以用 $n$ 张海报，因为每个建筑物的侧面都贴一张海报就是 $n$ 张海报了。

那么现在的难点就是如何减少海报的张数。建筑物侧面有可能为这样：

本来用四张海报贴的用三张海报就贴出来了（我只画了连起来的海报），但是如下不行：

虽然第一栋楼的高度和第四栋楼的高度一样，但是中间的楼比这两栋楼要矮，所以不能这么贴。

所以，当从第 $i$ 栋楼开始，可以一直贴到高度不大于（小于等于）第 $i$ 栋楼的楼。

那么怎样新开一张海报呢？无非只有两种情况：

1. 第一栋楼一定需要一张海报。

2. 当这栋楼的高度大于前一栋楼的高度或者小于前一栋楼的高度（或者说，当不能再覆盖的时候）。

所以，套进去算就可以了。

代码实现

如何写代码呢？首先，开一个栈，存楼的高度，如果栈不为空并且能够覆盖下一栋楼时，就将栈里的元素 pop 到不能再覆盖的楼的。如果可以新开的话，就答案加加，继续查询能否覆盖，别忘记无论如何都要存下这栋楼的高度。

代码很短，关键是把上面的搞懂：

#include<bits/stdc++.h>

using namespace std;

stack<int> stk;
int n, a[250005], sum;

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int x;
		cin >> x >> a[i];   //别忘记输入宽
	}
	for(int i = 1; i <= n; i++){
		while(!stk.empty() && stk.top() > a[i]){   //如果能覆盖下一栋楼
			stk.pop();   //那就pop掉
		}
		if(stk.empty() || stk.top() != a[i]){   //如果要新开一张海报
			sum++;
		}
		stk.push(a[i]);    //这栋楼的高度一定
	}
	cout << sum;
	return 0;
}

补充

1. 以上思路中始终没提宽一下，可能很多人猜到了，这题跟宽没关系。

2. 为什么本题用栈，因为要记录覆盖的楼，而正好符合栈先进后出的性质。

3. 拒绝抄袭题解，共创美好洛谷。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
long long top=0,n,num=0,i,j,k,stack[250100];
int main(){
    scanf("%lld",&n);
    for(i=1;i<=n;++i){
        scanf("%lld%lld",&j,&k);
        while(top>0&&k<=stack[top]){
            if(k==stack[top])num++;
            --top;
        }
        stack[++top]=k;
    }
    printf("%lld\n",n-num);
    return 0;
}