poj2823,应用单调队列解题的思路
发布日期:2021-08-28 13:15:43
浏览次数:16
分类:技术文章
本文共 2198 字,大约阅读时间需要 7 分钟。
关于单调队列的解释,这里有篇博文我认为讲得很好:
,可以参考。我自己简单的总结了一下单调队列这种数据结构的性质:
1 、在队列里的元素一定是value单调递增(或者递减),而index单调递增。所以 队列中的头元素要么最大,要么最小。
怎么保证这种性质呢,很简单,留在队列的元素在数组中并不是连续的。比如 array=1 4 7 3 2 ,在某个时刻,队列头元素为4,那么队列的结构有可能是4 3 2,而7就被跳过了。
2、 单调队列只允许从末尾加入元素,而允许从两端删除元素。
我这里就只贴代码,我这里用了两种方式来实现单调队列。针对poj2823那道题。
第一种:运用STL的Deque(双端队列):
- #include<deque> #include<stdio.h> using namespace std; #define M 1000005 int a[M]; char ch[2*M]; int n,k; int index; int getInt(){ int u=1,data=0; while(ch[index]<='0'||ch[index]>='9')index++; if(index>0&&ch[index-1]=='-')u=-1; while(ch[index]>='0'&&ch[index]<='9'){ data=data*10+ch[index]-'0'; index++; } return data*u; } int main(){ scanf("%d %d",&n,&k); int i; getchar(); gets(ch); index=0; for(i=1;i<=n;i++){ a[i]=getInt(); } deque<pair<int,int> > D(M); for(i=1;i<k;i++){ while(!D.empty()&&a[i]<=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); } for(i=k;i<=n;i++){ while(!D.empty()&&a[i]<=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); while(D.front().second<=i-k)D.pop_front(); printf("%d ",D.front().first); } printf("\n");D.clear(); for(i=1;i<k;i++){ while(!D.empty()&&a[i]>=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); } for(i=k;i<=n;i++){ while(!D.empty()&&a[i]>=D.front().first)D.pop_back(); D.push_back(make_pair<int,int>(a[i],i)); while(D.front().second<=i-k)D.pop_front(); printf("%d ",D.front().first); } return 0; }
这一种在poj上提交超时。
第二种:自己用数组实现单调队列:
- #include<stdio.h>
- #define M 2000005
- int a[M],Q[M],I[M];
- int i,n,k;
- void getMax(){
- int head=1,tail=0;
- for(i=1;i<k;i++){
- while(head<=tail&&Q[tail]<=a[i])tail--;
- tail++;
- Q[tail]=a[i];I[tail]=i;
- }
- for(i=k;i<=n;i++){
- while(head<=tail&&Q[tail]<=a[i])tail--;
- tail++;
- Q[tail]=a[i];I[tail]=i;
- while(I[head]<=i-k)head++;
- printf("%d ",Q[head]);
- }
- }
- void getMin(){
- int head=1,tail=0;
- for(i=1;i<k;i++){
- while(head<=tail&&Q[tail]>=a[i])tail--;
- tail++;
- Q[tail]=a[i];I[tail]=i;
- }
- for(i=k;i<=n;i++){
- while(head<=tail&&Q[tail]>=a[i])tail--;
- tail++;
- Q[tail]=a[i];I[tail]=i;
- while(I[head]<=i-k) head++;
- printf("%d ",Q[head]);
- }
- }
- int main(){
- scanf("%d %d",&n,&k);
- for(i=1;i<=n;i++)
- scanf("%d",&a[i]);
- getMin();
- printf("\n");
- getMax();
- return 0;
- }
这种就AC了。注明一下,第二种是我在网上找到的代码,不是自己写的!
转载地址:https://blog.csdn.net/weixin_33961829/article/details/85083102 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年02月29日 20时45分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java给xyz大小排序_java递归实现string xyz排序
2019-04-21
arctime必须要java_Arctime使用教程 Arctime常见问题解答
2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题
2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置
2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用
2019-04-21
java实验一目的_Java实验报告(实验一)
2019-04-21
php 内存泄露检测工具,php - 诊断内存泄漏 - 允许#bytes的内存大小耗尽
2019-04-21
Java 去除空格获取文件路径
2019-04-21
python 批量修改文件名称去除文件名中空格
2019-04-21
python 将文件名写入 txt文件
2019-04-21
python 3 读取文件txt 打印print
2019-04-21
python 查找txt文件中的字符串
2019-04-21
python 字符串替换 本地地址转换为网络地址
2019-04-21
Python3 http 服务任意目录 设定访问目录
2019-04-21
Python 移动鼠标到 句柄指定位置
2019-04-21
python窗口置顶 并输入中文
2019-04-21
Android studio 读取sd卡mp3 播放音乐
2019-04-21