题目链接
题目大意
Byteburg市东边的建筑都是以旧结构形式建造的:建筑互相紧挨着,之间没有空间.它们共同形成了一条长长的,从东向西延伸的建筑物链(建筑物的高度不一).Byteburg市的市长Byteasar,决定将这个建筑物链的一侧用海报覆盖住.并且想用最少的海报数量,海报是矩形的.海报与海报之间不能重叠,但是可以相互挨着(即它们具有公共边),每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖(意思是:海报需要将一侧全部覆盖,并且不能超出建筑物链)
题解
这道题是单调栈的入门经典题
我们发现:答案与宽度是没有关系的,于是我们只需要按高度维护一个单调递增的栈。
如果发现当前高度已经在栈中,就不需要另外一张海报了。
于是用一个ans变量记录一下,最后用总海报数减去不需要另外的海报数便是答案。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| #include < cstdio > #include < cstring > #include < algorithm > using namespace std; const int maxn=250005; long long n,a[maxn],stack[maxn],top=0,ans=0; int main() { scanf("%lld",&n); for(int i=1,x;i<=n;i++) scanf("%d%lld",&x,&a[i]); for(int i=1;i<=n;i++) { while(top&&stack[top]>a[i]) top--; if(stack[top]==a[i]) ans++; stack[++top]=a[i]; } printf("%lld\n",n-ans); return 0; }
|