单调队列小结

单调队列

故名思义,单调队列旨在维护一个队列,其中元素始终以某一关键字单调的顺序排列

单调队列的思想广泛用于最优解的维护,用于优化 1D/1D 动态规划

朝花中学 OI 队的奋斗历程——浅谈单调队列

[NOIP2016] 蚯蚓

优先队列

每次取最大,容易想到大根堆;

把蚯蚓的生长转化为刚切的两只蚯蚓长度 的单点修改,输出的时候把 加回来即可

复杂度 .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,q,u,v,t;
priority_queue<int> q;// 优先队列
int main(){scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    for(ll i=1,a;i<=n;i++){scanf("%d",&a);
        q.push(a);
    }
    for(ll i=0;i<m;i++){if((i+1)%t==0)printf("%d",q.top()+i*q);// 每 t 秒输出一次
        ll x,now=pq.top();q.pop();
        now+=i*q;// 把长度加回来,方便分割操作
        x=now*u/v;// 分割
        q.push(x-q-i*q),q.push(now-x-q-i*q);// 长度减回去,再减一个 q,然后入队
    }
    puts("");
    ll t2=1;
    while(!q.empty()){if(t2%t==0)printf("%d",q.top()+m*q);
        q.pop();t2++;}
    return 0;
}

单调队列

明确两点:

把蚯蚓生长转化为新的蚯蚓倒退生长之后,每一次取出的蚯蚓的长度单调递减,因为越切越短嘛

于是,对于先后被切的蚯蚓 ,显然有 ,因为按比例切割,总长度长的,自然切得就长嘛

于是,我们发现原来的蚯蚓 ,被切后的 形成的队列 ,被切后的 形成的队列 分别单调;

那么维护三个单调队列,每次切完后分别加到 队尾即可( 会越来越小)

复杂度 .

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+5,M=7e6+6,_INF=-1e9;
int n,m,q,u,v,t;
int a[N],cur;
queue<int> b,c;
int main(){scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    cur=n;// 队首
    for(int i=1;i<=m;i++){
        // 选最大的
        int k=_INF,p=0;
        if(cur&&a[cur]>k)k=a[cur],p=1;
        if(b.size()&&b.front()>k)k=b.front(),p=2;
        if(c.size()&&c.front()>k)k=c.front(),p=3;
        k+=(i-1)*q;// 真正长度
        if(i%t==0)printf("%d",k);
        // 切蚯蚓
        if(p==1)cur--;
        else if(p==2)b.pop();
        else c.pop();
        int x=(long long)k*u/v,y=k-x;
        b.push(x-i*q),c.push(y-i*q);// 先减掉增加的,再 -q
    }
    puts("");
    int tot=0;
    while(cur||b.size()||c.size()){
        tot++;
        // 选最大的
        int k=_INF,p=0;
        if(cur&&a[cur]>k)k=a[cur],p=1;
        if(b.size()&&b.front()>k)k=b.front(),p=2;
        if(c.size()&&c.front()>k)k=c.front(),p=3;
        if(tot%t==0)printf("%d",k+m*q);
        if(p==1)cur--;
        else if(p==2)b.pop();
        else c.pop();}
    return 0;
}

[LuoguP1565] 牛宫

首先说明,数据范围 <=200

先枚举矩形的上下边缘,然后将中间的每一列的数分别加在一起,变成一个序列 a[]。

对序列 a 做前缀和处理,问题转化成,求使得 最大的 ,满足

再维护一个单调递减的队列。每次插入的时候与队尾的元素做比较,如果比队尾元素大,就不入队;否则入队。

每次在队列上二分查找,更新答案即可。

总时间复杂度 .

最后,全程开 long long!

p.s. 不开 long long 全 WA,开 long long 全 AC

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,ans=0,qp[201][201];

ll low_bound(ll *arr,ll l,ll r,ll v){while(l<r){ll mid=(l+r)>>1;
        if(v>arr[mid])r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){scanf("%lld",&qp[i][j]);
            qp[i][j]+=qp[i-1][j];// 纵向前缀和
        }
    }
    for(ll i=0;i<n;i++){for(ll j=i+1;j<=n;j++){// 上下边界
            ll q[201],p[201],fr=1,bk=1;// 维护单调队列
            ll pre=0;// 当前的前缀和
            q[1]=p[1]=0;// 初始时有一个 0
            for(ll k=1;k<=m;k++){pre+=qp[j][k]-qp[i][k];// 当前的前缀和
                if(pre<q[bk])q[++bk]=pre,p[bk]=k;// 判断并入队
                ll t=(k-p[low_bound(q,fr,bk,pre)])*(j-i);// 二分查找
                ans=max(ans,t);// 更新答案 
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

  转载请注明: Sshwy's Blog 单调队列小结

 上一篇
搜索小结 搜索小结
搜索概述搜索问题的解,其实就是在问题对应的状态空间中进行映射与遍历. 使用递归,循环,数据结构等对状态空间的单调性,对称性,有解性进行排列归纳,加以搜索,以快速找到问题的答案 LuoguP1120 小木棍DFS 剪枝,在洛谷的毒瘤时间范围下
2018.12.19
下一篇 
贪心小结 贪心小结
小 TAG观察(贪心思路) 猜测(减少决策数量) 证明(从最优解转化为贪心解,并且不改变最优性质,从而证明) 多个贪心组合 贪心与非线性算法 贪心的单调性 贪心性质 贪心算法是一种形式及其多样的算法。它的应用方式很广,简单的简单,难的难。
2018.12.19
  目录