单调栈

——单调递增或单调减的栈,跟单调队列差不多,但是只用到它的一端,利用它可以用来解决一些 ACM/ICPC 和 OI 的题目,如 RQNOJ 的诺诺的队列等。


· 功能:

利用单调栈,可以找到从左/右遍历第一个比它小/大的元素的位置


· 模拟:

递增;1,5,2,7,3.

1:1

2:1,5

3:1,2

4:1,2,7

5:1,2,3


· 代码:

Stack<int> S;
for(int i=1 ;i<=n ;i++)
{
    while(S.size()&&a[S.top()]>=a[i])
        S.pop();
    if(S.empty())
    L[i]=0;
    else
        L[i] = S.top();
    S.push(i);
}

虽然说还是手打好一些……


· 例题:

序列问题 (bzoj1345)

题目描述

对于一个给定的序列 a1,…,an,我们对它进行一个操作 reduce(i),该操作将数列中的元素 ai 和 ai+1 用一个元素 max (ai,ai+1) 替代,这样得到一个比原来序列短的新序列。这一操作的代价是 max(ai,ai+1)。进行 n-1 次该操作后, 可以得到一个长度为 1 的序列。我们的任务是计算代价最小的 reduce 操作步骤,将给定的序列变成长度为 1 的序列。

输入

第一行为一个整数 n( 1 <= n <= 1,000,000 ),表示给定序列的长度。 接下来的 n 行,每行一个整数 ai(0 <=ai<= 1, 000, 000, 000),为序列中的元素。

输出

只有一行,为一个整数,即将序列变成一个元素的最小代价。

手打是这样滴……

scanf("%lld",&n);
while(n--)
{
    scanf("%lld",&m);
    while(m>=a[t]&&t)
    {
        if(m>=a[t-1]&&t>1)
        s+=a[t-1],t--;
        else
        s+=m,t--;
    }
    a[++t]=m;
}
while(t>1)
s+=a[--t];
cout<<s;

蒟蒻一枚,请各位神犇指导,$QQ:736731592$。

分类: 文章

1 条评论

Remmina · 2019年9月16日 1:00 下午

十分感谢您的投稿!
由于管理员不是咕咕咕(最近比较忙吧)就是退役了所以审核了比较久!很抱歉!
对于文章我个人建议可以将单调栈的模拟过程用文字更详细地说明~
_(:з」∠)_

Best regards

发表评论

电子邮件地址不会被公开。 必填项已用*标注