题解(单调队列模板) 2018寒假训练1 B.区间最小最大值
zhouwc
2018-02-25 09:49:27
问题 B: 区间最小最大值
时间限制: 2 Sec 内存限制: 128 MB
[提交][状态][讨论版]
题目描述
给定n个元素，以及一个正整数w，求每段区间的最小最大值。这些区间为：[1,1+w-1], [2,2+w-1], ..., [n-w+1,n]。
例如8个元素为[1 3 -1 -3 5 3 6 7], w为3，那么有下列最小最大值：
区间
最小值
最大值
[1 3 -1] -3 5 3 6 7
-1
3
1 [3 -1 -3] 5 3 6 7
-3
3
1 3 [-1 -3 5] 3 6 7
-3
5
1 3 -1 [-3 5 3] 6 7
-3
5
1 3 -1 -3 [5 3 6] 7
3
6
1 3 -1 -3 5 [3 6 7]
3
7
输入
第一行输入n,w
第二行输入n个整数
输出
第一行输出区间最小值
第二行输出区间最大值
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
提示
1<=n<=10^6 1<=w<=n
10^-9 <= 元素 <= 10^9
题解
这题是单调队列。分别维护队首和队尾。
罗老师核心代码
```cpp
id队列存储下标
Q队列存储值
void minquery(){
//求最小值
int st=0, ed=0;
for(int i=1; i<=w; i++){ //先扫描到w，产生初始单调队列
while(st<ed && Q[ed]>a[i]) ed--;
ed++;
Q[ed]=a[i];
id[ed]=i;
}
for(int i=w+1; i<=n; i++){
while(st<ed && id[st+1]<i-w) st++; //维护队首
printf("%d ",Q[st+1]);
while(st<ed && Q[ed]>a[i]) ed--; //维护队尾
ed++;
Q[ed]=a[i];
id[ed]=i;
}
while(st<ed && id[st+1]<n+1-w) st++;
printf("%d\n",Q[st+1]);
}
```
我的代码
```cpp
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1000005],head,tail,n,m,a[1000005];
int min()
{
head=1; tail=0;
for (int i=1;i<=n;i++)
{
while(head<=tail&&f[head]+m<=i) head++;
while(head<=tail&&a[i]<a[f[tail]]) tail--;
f[++tail]=i;
if(i>=m) printf("%d",a[f[head]]);
if (i!=n&&i>=m) printf(" ");
}
printf("\n");
return 0;
}
int max()
{
head=1; tail=0;
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++)
{
while(head<=tail&&f[head]+m<=i) head++;
while(head<=tail&&a[i]>a[f[tail]]) tail--;
f[++tail]=i;
if(i>=m) printf("%d",a[f[head]]);
if (i!=n&&i>=m) printf(" ");
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
min();
max();
}
```