NOIP复赛复习（十六）栈与双端队列的运用

定期推送信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，融科教育信息学竞赛培训等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！

一、栈的运用

通过活用栈等简单的数据结构，可以巧妙地降低一些算法的复杂度。

POJ 2559

题意：n个宽度为1，高度为h[i]（1<=i<=n）组成的柱形图，求里面包含的长方形的最大面积； 

思路：如果确定了长方形的左端点L和右端点R，那么最大可能高度就是min{h[i]|L<=i（一般做题区间都是左闭右开，便于计算），时间复杂度O(n^3)，考虑优化区间最小值，可以降为O(n^2)，但仍然无法在规定时间内求出答案。

考虑换种思路假设面积最大的长方形的左端为L，右端为R，高度为H。如果h[L-1]>=H，那么左端点可以更新为L-1，从而得到更大的长方形，与假设矛盾，故h[L-1]。同理，h[R]，并且高度H=min{h[i]|L<=i。

做法：我们可以固定h[i]向左右方向延伸，则可以定义两个单调栈：L[i]=(j<=i并且h[j-1]的最大的j)   R[i]=(j并且h[j]>h[i]的最小的j)

在计算L[i]时，首先，当栈顶的元素j满足h[j]>=h[i]，则不断取出栈顶元素。若栈为空，则L[i]=0，若h[j]，则L[i]=j+1.然后把i压入栈中。

时间复杂度：由于栈的压入和弹出操作都是O（n）次，因此整个算法的时间复杂度为O（n）。对于R也可以用同样的方法计算。

 

#include

typedef long long ll;

const int maxn=100005;

ll a[maxn];

ll st[maxn];

ll l[maxn];

ll r[maxn];

ll max(ll aa,ll bb){

    return aa>bb?aa:bb;

}

int main(){

    int n;

//  freopen('in9.txt','r',stdin);

   while(scanf('%d',&n)!=-1&&n){

        for(int i=0;i

            scanf('%lld',&a[i]);

        }

        int top=0;

        for(int i=0;i

           while(top&&a[st[top-1]]>=a[i]){

                top--;

            }

            l[i]=top==0?0:st[top-1]+1;

            st[top++]=i;

        }

        top=0;

        for(int i=n-1;i>=0;i--){

           while(top&&a[st[top-1]]>=a[i]){

                top--;

            }

            r[i]=top==0?n:st[top-1];

            st[top++]=i;

        }

        ll ans=0;

        for(int i=0;i

            ans=max(ans,((r[i]-l[i])*a[i]));

        }

        printf('%lld\n',ans);

    }

    return 0;

}

  

二、双端队列的运用 

队列是一种只允许在一端删除而在另一端插入的数据结构。双端队列(Deque)是队列的一种拓展，它可以在队列的两端进行插入和删除，它是限定插入和删除操作在表的两端进行的线性表，是一种具有队列和栈的性质的数据结构。

 

POJ 3709

题意：有一个不递减的序列，现在要把这些数分成若干个部分，每部分不能少于m个数。每部分的权值为所有数减去该部分最小的数的和。求最小的总权值。 

首先不难得出，a0是最小的值，为了使操作的次数较小，我们不可能把最小值拿着减。所以我们发现，对于a0这样的较小的项，我们可以选择从小到大来选择需要减少到a0的项。设dpi为只考虑前i项的前提下最少的操作次数，则有dpi=min{dpj+(a[j+1]-a[j])+…+(a[i−1]-a[j])},其中0≤j≤i−k。

直接计算自然没问题，但是O3的复杂度不太好的样子，于是考虑优化：

例如我们记一个前缀和，

Si=a[0]+...+a[i−1]

有dpi=min{dpj+S[i]-S[j+1]-aj*(i-j-1)} 
观察方程我们可以发现,若我们设一个函数（用x替换i）fj(x)=−aj∗x+dp[j]−S[j+1]+aj∗(j+1)，则有dp[i]=S[i]+minfj(i),于是计算dp[n]就变为了在i-k+1条直线中寻找x=i的最小值就好了。 
于是我们考虑用双端队列去维护所有可能成为最小值的直线的集合，并以从小到大的顺序排列。那么我们如何判断要去掉某条直线呢？

设：

f1(x)=a1∗x+b1 
f2(x)=a2∗x+b2 
f3(x)=a3∗x+b3

我们有(a2−a1)∗(b3−b2)≥(b2−b1)∗(a3−a2) 时，f2为要排除的直线。 

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

const ll maxn=505000;

ll cas=0;

ll n,k;

ll a[maxn];

ll deq[maxn];//虽然是双端队列但存的是值

ll dp[maxn*10];

ll sh[maxn];//前缀和

bool check(ll f1,llf2,ll f3)

{

    ll a1=-a[f1];

    ll b1=dp[f1]-sh[f1+1]+a[f1]*(f1+1);

    ll a2=-a[f2];

    ll b2=dp[f2]-sh[f2+1]+a[f2]*(f2+1);

    ll a3=-a[f3];

    ll b3=dp[f3]-sh[f3+1]+a[f3]*(f3+1);

    return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);

}

ll f(ll j,ll x)

{

    return -a[j]*x+dp[j]-sh[j+1]+a[j]*(j+1);

}

int main()

{

   //freopen('1.in','r',stdin);

   //freopen('2.out','w',stdout);

    scanf('%lld',&cas);

    for(ll z=0;z

    {

        memset(sh,0,sizeof(sh));

        memset(a,0,sizeof(a));

        memset(dp,0,sizeof(dp));

        memset(deq,0,sizeof(deq));

       scanf('%lld%lld',&n,&k);

        for(ll i=0;i

        {

            scanf('%lld',&a[i]);

        }

        for(ll i=0;i

        {

            sh[i+1]=sh[i]+a[i];

        }

        ll s=0;

        ll t=1;

        deq[s]=0;

        dp[0]=0;

        for(ll i=k;i<=n;i++)

        {

            if(i-k>=k)

            {

                while(s+1

                {

                    t--;

                }

                deq[t]=i-k;

                t++;

            }

            while(s+1=f(deq[s+1],i))

            {

                s++;

            }

            dp[i]=sh[i]+f(deq[s],i);

        }

        printf('%lld\n',dp[n]);

    }

    return 0;

}

---