单调队列

fzoj1894 志愿者选拔
裸的单调队列,注意出队的时候,只有当当前删除的人的下标等于优先队列中队首的人的下标,才出队

#include<stdio.h>
#include<string.h>
char s[10];
int q[1000000+10],head,tail;
int num[1000000+10];
int main()
{
    int i,j,t,val;
    scanf("%d",&t);
    while(t--)
    {
        head=0;tail=-1;
        int index=0,index2=0;
        scanf("%s",s);
        while(~scanf("%s",s) && strcmp(s,"END")!=0)
        {
            if(s[0]=='C')
            {
                index++;
                scanf("%s %d",s,&val);
                while(tail>=head && val>=q[tail]) tail--;
                q[++tail]=val;num[tail]=index;
            }
            else if(s[0]=='G')
            {
                index2++;
                if(num[head]==index2) head++;
            }
            else
            {
                if(head>tail) puts("-1");
                else printf("%d\n",q[head]);
            }
        }
    }
    return 0;
}

poj2823 Sliding Window
经典的单调队列应用
f[x]=opt{a[i]|bound[x]<=i<=x}

#include<stdio.h>
#include<string.h>
#define maxn 1000000+10
int a[maxn],q[maxn];
int num[maxn];
int head,tail;
int main()
{
    int i,j;
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        head=0;tail=-1;
        for(i=1;i<=(k<=n?k:n);i++)
        {
            while(head<=tail && q[tail]>=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
        }
        printf("%d",q[head]);
        for(i=k+1;i<=n;i++)
        {
            while(head<=tail && q[tail]>=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
            while(num[head]<i-k+1) head++;
            printf(" %d",q[head]);
        }
        printf("\n");

        head=0;tail=-1;
        for(i=1;i<=(k<=n?k:n);i++)
        {
            while(head<=tail && q[tail]<=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
        }
        printf("%d",q[head]);
        for(i=k+1;i<=n;i++)
        {
            while(head<=tail && q[tail]<=a[i]) tail–;
            q[++tail]=a[i];num[tail]=i;
            while(num[head]<i-k+1) head++;
            printf(" %d",q[head]);
        }
        printf("\n");



    }
    return 0;
}

hdoj3415 Max Sum of Max-K-sub-sequence
经典单调队列
dp[i]=sum[i]-sum[j]=sum[i]-min{sum[j]|i-k<=j<=i-1}
加输入外挂才能过,,不然TLE。。囧~

#include<stdio.h>
#include<string.h>
#define maxn 200000+10
int a[maxn],q[maxn],head,tail;
int num[maxn];
int path[maxn];
void scan(int &num)//对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-');
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');//去负号后空格
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg) num=0-num;
}

int main()
{
    int i,j;
    int t,n,k;
    scan(t);
    while(t--)
    {
        scan(n);scan(k);
        head=0;tail=-1;
        a[0]=0;
        for(i=1;i<=n;i++) {scan(a[i]);a[i+n]=a[i];}
        for(i=1;i<=2*n;i++) a[i]+=a[i-1];
        q[++tail]=a[0];num[tail]=0;
        for(i=1;i<=2*n;i++)
        {
            while(num[head]<i-k) head++;
            path[i]=num[head]+1;
            while(head<=tail && a[i]<q[tail]) tail--;
            q[++tail]=a[i];num[tail]=i;
        }
        int ans=-1000000000,begin=maxn,end,len;
        for(i=1;i<=2*n;i++)
        {
            if(a[i]-a[path[i]-1]>ans)
            {
                ans=a[i]-a[path[i]-1];len=i-path[i]+1;
                begin=path[i]>n?path[i]-n:path[i];
                end=i>n?i-n:i;
            }
            else if(a[i]-a[path[i]-1]==ans)
            {
                if((path[i]>n?path[i]-n:path[i])<begin)
                {
                    len=i-path[i]+1;
                    begin=path[i]>n?path[i]-n:path[i];
                    end=i>n?i-n:i;
                }
                else if((path[i]>n?path[i]-n:path[i])==begin && i-path[i]+1<len)
                {
                    len=i-path[i]+1;
                    begin=path[i]>n?path[i]-n:path[i];
                    end=i>n?i-n:i;
                }
            }
        }
        printf("%d %d %d\n",ans,begin,end);


    }
    return 0;
}

发表评论

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

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>