双端队列

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int M = 1e6 + 10 , inf = 0x3f3f3f3f ;
 4 int s ;
 5 int n , k ;
 6 int a[M] ;
 7 int b[M] , tot ;
 8 void solve () {
 9     deque<int> q ;
10     deque<int>::iterator it ;
11     for (int i = 0 ; i < k ; i ++) {
12         if (q.empty ()) q.push_back (i);
13         else {
14             it = q.end () - 1 ;
15             while (*it >= a[i] && !q.empty ()) {
16                 q.pop_back () ;
17                 it -- ;
18             }
19             q.push_back (i) ;
20         }
21     }
22     b[tot++] = q.front () ;
23     if (q.front () == 0) q.pop_front () ;
24     for (int i = k ; i < n ; i ++) {
25         if (q.empty ()) q.push_back (i) ;
26         else {
27             it = q.end () - 1 ;
28             while (*it >= a[i] && !q.empty ()) {
29                 q.pop_back () ;
30                 it -- ;
31             }
32             q.push_back (i) ;
33         }
34         b[tot++] = q.front () ;
35         if (q.front () == i-k+1) q.pop_front () ;
36     }
37     for (int i = 0 ; i < tot ; i ++) {
38         printf ("%d " , a[b[i]]) ;
39     } puts ("") ;
40 }
41 
42 int main () {
43     cin >> n >> k ;
44     for (int i = 0 ; i < n ; i ++) cin >> a[i] ;
45     solve () ;
46     return 0 ;
47 }
View Code