单调队列

发布于 2019-03-02  220 次阅读


学了一些有关单调队列的知识,这里放一些代码和一些需要注意的细节。
head=1,tail=0;这样可以防未进队就出队。
注意头部出队时可能为空。
而因为一系列操作,队列中的序号也是单调的。
但是需要注意的是head与tail也可以等于1,这样可以在决策单调性时可以使用。具体见以下例1与例3.

//fzu p 1894
#include <stdio.h>
const int MAX = 1000010;

using namespace std;

typedef long long LL;

char name[10],order[20];
LL value[MAX];
int T,q[MAX],head,tail;
int main(){
	scanf("%d",&T);
	scanf("%s",order);
	while(T--)
	{
	    int n=0,g=0;
		head=1,tail=0;
		while(scanf("%s",order)&&order[0]!='E')
		{
			if(order[0]=='C')
			{
			scanf("%s%d",name,&value[++n]);
			while(head<=tail&&value[q[tail]]<value[n])--tail;
			q[++tail]=n;
			}
			else if(order[0]=='Q'){if(head<=tail)printf("%d\n",value[q[head]]);else printf("-1\n");}
			else if(order[0]=='G'){++g;if(head<=tail&&q[head]==g)++head;}
		}
	}
	return 0;
}

poj 2823 g++
#include <cstring>
#include <cstdlib>
#include <stdio.h>
using namespace std;
const int MAX = 1000010;
inline int read(){
  int x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}
int v[MAX],q[MAX],head,tail,n,k;
int main()
{
  int i;
  n=read();k=read();
  for(i=1;i<=n;++i)
    v[i]=read();
  if (k==1)
  {
    for (int i = 1; i <= n; ++i)
    {
      printf("%d ",v[i] );
    }
    printf("\n");
    for (int i = 1; i <= n; ++i)
    {
      printf("%d ",v[i] );
    }
    return 0;
  }
  head=1,tail=0;
  for(i=1;i<=n;++i)
  {
    while(head<=tail&&q[head]<i-k+1)
      ++head;
    while(head<=tail&&v[q[tail]]>=v[i])
      --tail;
    q[++tail]=i;
    if (i>=k)
    {
      printf("%d ",v[q[head]]);
    }
  }
    printf("\n");
    memset(q,0,sizeof(q));
  head=1,tail=0;
  for (i=1;i<=n;++i)
  {
    while(head<=tail&&q[head]<i-k+1)
      ++head;
    while(head<=tail&&v[q[tail]]<=v[i])
      --tail;
      q[++tail]=i;
    if(i>=k)
    {
      printf("%d ",v[q[head]]);
    }
  }
  return 0;
}
#include <bits/stdc++.h>

const int MAX = 1000010;

using std::scanf;
using std::printf;

inline int min(int x,int y){
	return x<y?x:y;
}

int f[MAX],q[MAX];
int main(){
	int n,m,i,j,head,tail,best = MAX;
	scanf("%d%d",&n,&m);
	head=tail=1;
	for(i=1;i<=n;++i)
	{ 
		int w;scanf("%d",&w);
		while(head<=tail&&q[head]<i-m)++head;
		f[i]=f[q[head]]+w;
		while(head<=tail&&f[q[tail]]>f[i])--tail;
		q[++tail]=i;
	}
	for(j=n-m+1;j<=n;j++)best=min(best,f[j]);
	printf("%d\n",best);
	return 0;
}

我是一个局部环,你是我的唯一极大理想。