题目链接

luogu P3467

题目描述

$Byteburg$市东边的建筑都是以旧结构形式建造的：建筑互相紧挨着，之间没有空间。它们共同形成了一条长长的、从东向西延伸的建筑物链（建筑物的高度不一）。$Byteburg$市的市长$Byteasar$，决定将这个建筑物链的一侧用海报覆盖住。并且想用最少的海报数量，海报是矩形的。海报与海报之间不能重叠，但是可以相互挨着（即它们具有公共边），每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖（意思是：海报需要将一侧全部覆盖，并且不能超出建筑物链）

输入格式

第一行为一个整数$n(1\le n\le 250000)$,表示有$n$个建筑,接下来$n$行中,第$i$行表示第$i$个建筑物的宽 d i d_i di​与高 w i ( 1 ≤ d i , w i ≤ 1 0 9 ) w_i(1≤d_i,w_i\le 10^9) wi​(1≤di​,wi​≤109)，中间由一个空格隔开。

输出格式

第一个为一个整数，表示最少需要几张海报。

输入输出样例

输入
5
1 2
1 3
2 2
2 5
1 4
输出
4

说明/提示

题目简述：$N$个矩形，排成一排。现在希望用尽量少的矩形海报$Cover$住它们。

题意

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

思路

首先，我们将样例绘制成一个图表


第一张为建筑物的示意图，第二张为海报$Cover$的示意图
可以发现，建筑物所谓的宽度 d i d_i di​是没有用的，因为海报理论上是无限宽的
解决了宽度后我们只需关注高度就行了
海报增加的条件——在弹出栈顶的所有比它高的建筑后，若当前建筑高度与栈顶建筑不相等，答案增加

1. 根据第二张图形，可以总结出：当前建筑的高度如果突出，那肯定要多用一张海报（如海报$2,4$）
2. 就算不突出，也能对后面高度大于等于它的连续的建筑产生贡献（如海报$1,3$）

#include
using namespace std;
#define int long long
stack<int>st;
int tmp,n,h[250010]={-1},ans;
signed main(){scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&tmp,&h[i]);st.push(0);//栈底要有一个最小值，防止访问报错for(int i=1;i<=n;i++){while(!st.empty()&&h[st.top()]>h[i])st.pop();if(h[st.top()]!=h[i])ans++;//符合答案增加的条件st.push(h[i]);}printf("%lld",ans);return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！