poj2823单调队列
2024-08-21 10:51:49
这个裸题,滑动窗口求最大最小值,单调队列来两边,一次单调递增q[s]就是最小值,一次单调递减q[s]就是最大值
cin会超时,解除同步也没用。。。
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; int a[N],q[N];
int minn[N],maxx[N];
int main()
{
/* ios::sync_with_stdio(false);
cin.tie(0);*/
int n,k;
while(~scanf("%d%d",&n,&k)){
for(int i=;i<n;i++)scanf("%d",&a[i]);
int s=,t=;
for(int i=;i<n;i++)
{
while(s<t&&a[i]>a[q[t-]])t--;
q[t++]=i;
if(s<t&&q[t-]-q[s]>=k)s++;
/* for(int j=s;j<t;j++)cout<<a[q[j]]<<" ";
cout<<endl;*/
minn[i]=a[q[s]];
}
s=,t=;
for(int i=;i<n;i++)
{
while(s<t&&a[i]<a[q[t-]])t--;
q[t++]=i;
if(s<t&&q[t-]-q[s]>=k)s++;
/* for(int j=s;j<t;j++)cout<<a[q[j]]<<" ";
cout<<endl;*/
maxx[i]=a[q[s]];
}
for(int i=k-;i<n;i++)
printf("%d%c",maxx[i],i==n-?'\n':' ');
for(int i=k-;i<n;i++)
printf("%d%c",minn[i],i==n-?'\n':' ');
}
return ;
}
最新文章
- HTMl链接- target/ name
- Understanding Weak References
- android中ListView_SimpleAdapter
- 理解Php中的Static
- beini破解无线
- (转)iOS项目的目录结构和开发流程
- UE4 Fade out Mesh
- JAVA提高十:ArrayList 深入分析
- android自定义状态栏颜色
- 跟我学ASP.NET MVC之二:第一个ASP.NET MVC程序
- C#机器学习之判断日报是否合格
- Java类文件的结构
- js的作用域题
- python2和3的区别
- disconf原理 “入坑”指南
- 3D打印开源软件Cura分析(1) 【转】
- ruby-from-other-languages
- (未完成&#128067;)You Don&#39;t Know JS: Scope &; Closures (第5章: Scope &; Closures)
- IDEA搭建Spring框架环境
- Django商城项目笔记No.18商品部分-数据表创建