[b][b][b][b][size=large][size=medium]一、 什么是单调(双端)队列
单调队列,顾名思义,就是一个元素单调的队列,那么就能保证队首的元素是最小(最大)的,从而满足动态规划的最优性问题的需求。
单调队列,又名双端队列。双端队列,就是说它不同于一般的队列只能在队首删除、队尾插入,它能够在队首、队尾同时进行删除。
【单调队列的性质】
一般,在动态规划的过程中,单调队列中每个元素一般存储的是两个值:
1、在原数列中的位置(下标)
2、 他在动态规划中的状态值
而单调队列则保证这两个值同时单调。
从以上看,单调队列的元素最好用一个类来放,不这样的话,就要开两个数组。。。
单调队列:单调队列 即保持队列中的元素单调递增(或递减)的这样一个队列,可以从两头删除,只能从队尾插入。单调队列的具体作用在于,由于保持队列中的元素满足单调性,对手元素便是极小值(极大值)了。
http://poj.org/problem?id=2823
//poj-2823--单调队列
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX = 1000001;
//两个单调队列
int dq1[MAX]; //一个存单调递增
int dq2[MAX]; //一个存单调递减
int a[MAX];
inline bool scan_d(int &num) // 这个就是 加速的 关键了
{
char in;bool IsN=false;
in=getchar();
if(in==EOF)
return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-') { IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9')
{
num*=10,num+=in-'0';
}
if(IsN)
num=-num;
return true;
}
int main(void)
{
int i,n,k,front1,front2,tail1,tail2,start,ans;
while(scanf("%d %d",&n,&k)!=EOF)
{
for(i = 0 ; i < n ; ++i)
scan_d(a[i]);
front1 = 0, tail1 = -1;
front2 = 0, tail2 = -1;
ans = start = 0;
for(i = 0 ; i < k ; ++i)
{
while(front1 <= tail1 && a[ dq1[tail1] ] <= a[i]) //当前元素大于单调递增队列的队尾元素的时候,队尾的元素依次弹出队列,直到队尾元素大于当前当前元素的时候,将当前元素插入队尾
--tail1;
dq1[ ++tail1 ] = i; //只需要记录下标即可
while(front2 <= tail2 && a[ dq2[tail2] ] >= a[i]) //当前元素小于单调递减队列的队尾元素的时候,队尾的元素依次弹出队列,直到队尾元素小于当前当前元素的时候,将当前元素插入队尾
--tail2;
dq2[ ++tail2 ] = i; //只需要记录下标即可
}
printf("%d ",a[ dq2[ front2 ] ]);
for( ; i < n ; ++i)
{
while(front2 <= tail2 && a[ dq2[tail2] ] >= a[i])
--tail2;
dq2[ ++tail2 ] = i;
while(dq2[ front2 ] <= i - k)
++front2;
if(i != n-1)
printf("%d ",a[ dq2[ front2 ] ]);
}
printf("%d\n",a[ dq2[ front2 ] ]);
//输出最大值
printf("%d ",a[ dq1[ front1 ] ]);
for(i=k ; i < n ; ++i)
{
while(front1 <= tail1 && a[ dq1[tail1] ] <= a[i])
--tail1;
dq1[ ++tail1 ] = i;
while(dq1[ front1 ] <= i - k)
++front1;
if(i != n-1)
printf("%d ",a[ dq1[ front1 ] ]);
}
printf("%d\n",a[ dq1[ front1 ] ]);
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=3530 Subsequence
/*
题意:给出一个序列,求最长的连续子序列,使得 M<=Max-Min<=K
n <= 10^5
依次枚举剩下的N-1个元素,并且将当前未入队的第一个元素和队尾元素比较,当且仅当队列为非空并且队尾元素的值小于当前未入队的元素时,
将队尾元素删除(也就是队尾指针-1),因为当前的元素比队尾元素大,所以在区间内队尾元素不会是最大值了。
重复这个过程直到队列空或者队尾元素比当前元素大,
*/
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX = 100001;
//两个单调队列
int dq1[MAX]; //一个存单调递增
int dq2[MAX]; //一个存单调递减
int a[MAX];
inline bool scan_d(int &num) // 这个就是 加速的 关键了
{
char in;bool IsN=false;
in=getchar();
if(in==EOF)
return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-') { IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9')
{
num*=10,num+=in-'0';
}
if(IsN)
num=-num;
return true;
}
int main(void)
{
int i,n,m,k,front1,front2,tail1,tail2,start,ans;
while(scanf("%d %d %d",&n,&m,&k) != EOF)
{
for(i = 0 ; i < n ; ++i)
scan_d(a[i]);
front1 = 0, tail1 = -1;
front2 = 0, tail2 = -1;
ans = start = 0;
for(i = 0 ; i < n ; ++i)
{
while(front1 <= tail1 && a[ dq1[tail1] ] <= a[i]) //当前元素大于单调递增队列的队尾元素的时候,队尾的元素依次弹出队列,直到队尾元素大于当前当前元素的时候,将当前元素插入队尾
--tail1;
dq1[ ++tail1 ] = i; //只需要记录下标即可
while(front2 <= tail2 && a[ dq2[tail2] ] >= a[i]) //当前元素小于单调递减队列的队尾元素的时候,队尾的元素依次弹出队列,直到队尾元素小于当前当前元素的时候,将当前元素插入队尾
--tail2;
dq2[ ++tail2 ] = i; //只需要记录下标即可
/*
Max - Min 为两个队列的队首之差
while(Max-Min>K) 看哪个的队首元素比较靠前,就把谁往后移动
*/
while(a[ dq1[front1] ] - a[ dq2[front2] ] > k)
{
if(dq1[front1] < dq2[front2] )
{
start = dq1[front1] + 1;
++front1;
}
else
{
start = dq2[front2] + 1;
++front2;
}
}
if(a[ dq1[front1] ] - a[ dq2[front2] ] >= m)
{
if(i - start +1 > ans)
ans = i - start + 1;
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
acm上关于寻找单调数的算法 自己写的,数组还可以进行优化
ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛
ACM题。关于顺序串的操作,请自行查找题目。该题比较简单故略去分析。
ACM ACM ACM ACM ACM讲义.ppt
ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板AACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM ...
ACM PRO ACM PROACM PRO ACM PROACM PRO ACM PRO
包含近几年多道ACM面试题目,希望有所帮助
acm模板acm模板acm模板acm模板acm模板acm模板acm模板acm模板
ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码
ACM地址 ACM地址 ACM地址 ACM地址 ACM地址
acm经典题库acm经典题库acm经典题库
ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版ACM大数模版
上海交大ACM模板 考研复试机试参考资料
ACM练习建议 ACM练习建议 ACM练习建议
acm课件1acm课件1acm课件1acm课件1acm课件1acm课件1acm课件1acm课件1acm课件1
ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM...
杭电ACM分类杭电ACM分类杭电ACM分类杭电ACM分类
ACM培训资料 ACM培训资料 ACM培训资料 ACM培训资料
北大ACM分类,北大ACM分类 北大ACM分类