质量检测

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

题目

点这里

思路

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

代码

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;
}

结束了，谢谢观看！！