洛谷 P2032 扫描（单调队列）

传送门

解题思路

就是个简单的模板。

本来不想写题解的，但是这次单调队列写得好短呀！QAQ

AC代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 int n,k,a[1000005];
 6 deque<int> q;
 7 int main()
 8 {
 9     cin>>n>>k;
10     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
11     for(int i=1;i<=n;i++){
12         if(q.empty()) q.push_back(i);
13         else{
14             if(q.front()+k<=i) q.pop_front();
15             while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();
16             q.push_back(i);
17         }
18         if(i>=k) printf("%d
",a[q.front()]);
19     }
20     return 0;
21 }