---

layout: post
title: 洛谷试炼场 4-8单调队列
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 单调队列
- 洛谷

---

[P2698 USACO12MAR]花盆Flowerpot (二分+单调队列)

题解

二分区间

做两个单调队列记录最大最小值，如果差大于D就OK

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    int x,y;
    bool operator <(const node &a)const{
        return x<a.x;
    }
}a[maxn];
int n,d;
int qmax[maxn],qmin[maxn];
bool ok(int mid){
    int h1=1,h2=1,t1=0,t2=0;
    for(int i=1;i<=n;i++){
        while(h1<=t1&&a[i].y>a[qmax[t1]].y)t1--;
        qmax[++t1]=i;
        while(h2<=t2&&a[i].y<a[qmin[t2]].y)t2--;
        qmin[++t2]=i;
        while(h1<=t1&&a[i].x-a[qmax[h1]].x>mid)++h1;
        while(h2<=t2&&a[i].x-a[qmin[h2]].x>mid)++h2;
        if(a[qmax[h1]].y-a[qmin[h2]].y>=d)return true;
    }
    return false;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+1+n);
    int ans=-1,l=0,r=1e8;
    while(l<=r){
        int mid=(l+r)/2;
        if(ok(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

[HAOI2007]理想的正方形 （二维单调队列）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int value[1100][1100];
int qmin[1100],qmax[1100];
int hmin[1100][1100],hmax[1100][1100];
int lmin[1100][1100],lmax[1100][1100];
void print(int a,int b,int p[][1100]){
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            cout<<p[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int a,b,n;
    cin>>a>>b>>n;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            cin>>value[i][j];
        }
    }
    for(int i=1;i<=a;i++){
        int head1=1,tail2=0,head2=1,tail1=0;
        for(int j=1;j<=b;j++){
            while(head1<=tail1&&value[i][j]<value[i][qmin[tail1]])tail1--;qmin[++tail1]=j;
            while(head2<=tail2&&value[i][j]>value[i][qmax[tail2]])tail2--;qmax[++tail2]=j;
            while(j-qmin[head1]>=n)head1++;
            while(j-qmax[head2]>=n)head2++;
            if(j>=n)hmin[i][j-n+1]=value[i][qmin[head1]],hmax[i][j-n+1]=value[i][qmax[head2]];
        }
    }
   // cout<<endl;print(a,b,hmin);cout<<endl;print(a,b,hmax);cout<<endl;
    for(int i=1;i<=b-n+1;i++){
        int head1=1,tail2=0,head2=1,tail1=0;
        for(int j=1;j<=a;j++){
            while(head1<=tail1&&hmin[j][i]<hmin[qmin[tail1]][i])tail1--;qmin[++tail1]=j;
            while(head2<=tail2&&hmax[j][i]>hmax[qmax[tail2]][i])tail2--;qmax[++tail2]=j;
            while(j-qmin[head1]>=n)head1++;
            while(j-qmax[head2]>=n)head2++;
            if(j>=n)lmin[j-n+1][i]=hmin[qmin[head1]][i],lmax[j-n+1][i]=hmax[qmax[head2]][i];
        }
    }
  //  print(a,b,lmin);cout<<endl;print(a,b,lmax);
    int ans=inf;
    for(int i=1;i<=a-n+1;i++)
        for(int j=1;j<=b-n+1;j++)
            ans=min(ans,lmax[i][j]-lmin[i][j]);
    cout<<ans<<endl;
    return 0;
}

[P2564 SCOI2009]生日礼物 （尺取法）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct node{
    int kind;
    ll x;
    bool operator<(const node &a)const{
        return x<a.x;
    }
}my[maxn];
vector<node>ve;
int num[maxn];
int has[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        int tot;
        cin>>tot;
        ll w;
        while(tot--){
            cin>>w;
            ve.push_back(node{i,w});
        }
    }
    sort(ve.begin(),ve.end());
    ll st=0,ans=inf;deque<node>dq;
    for(int i=0;i<ve.size();i++){
        node now=ve[i];
        dq.push_back(now);
        num[now.kind]++;
        if(num[now.kind]==1)st++;
        while(st>=k){
            node head=dq.front();
            node tail=dq.back();
            ans=min(ans,tail.x-head.x);
            dq.pop_front();
            num[head.kind]--;
            if(num[head.kind]==0)st--;
        }
    }
    cout<<ans<<endl;
    return 0;
}

[P2569 SCOI2010]股票交易(单调队列优化DP)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m,ap,bp,as,bs,w,ans=0,f[2020][2020],head,tail,q[2020];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m>>w;
    memset(f,-inf,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>ap>>bp>>as>>bs;
        for(int j=0;j<=as;j++)f[i][j]=-1*j*ap;
        for(int j=0;j<=m;j++)f[i][j]=max(f[i][j],f[i-1][j]);
        if(i<=w)continue;
        head=1,tail=0;
        for(int j=0;j<=m;j++){
            while(head<=tail&&q[head]<j-as)head++;
            while(head<=tail&&f[i-w-1][q[tail]]+q[tail]*ap<f[i-w-1][j]+j*ap)tail--;
            q[++tail]=j;
            if(head<=tail)f[i][j]=max(f[i][j],f[i-w-1][q[head]]+q[head]*ap-j*ap);
        }
        head=1,tail=0;
        for(int j=m;j>=0;j--){
            while(head<=tail&&q[head]>j+bs)head++;
            while(head<=tail&&f[i-w-1][q[tail]]+q[tail]*bp<f[i-w-1][j]+j*bp)tail--;
            q[++tail]=j;
            if(head<=tail)f[i][j]=max(f[i][j],f[i-w-1][q[head]]+q[head]*bp-j*bp);

        }
    }
    for(int i=0;i<=m;i++)ans=max(ans,f[n][i]);
    cout<<ans<<endl;
    return 0;
}