质量检测

题目

点这里

思路

看完题目之后发现这不就是一道单调队列求区间最小值吗?
这还不简单吗?
单调队列又短又快,不选它那选谁?

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int n,m,a[maxn];
deque<int>que;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=n;i++){
while(que.size()&&a[i]<=a[que.back()]) que.pop_back();//去尾
while(que.size()&&i-que.front()>=m) que.pop_front();//去头
que.push_back(i);//加入当前的位置
if(i>=m) printf("%d\n",a[que.front()]);//输出
}//四步结束...
return 0;
}

结束了,谢谢观看!!