[POJ2823]Sliding Window(单调队列)

题目链接:

http://poj.org/problem?id=2823

题意:

给你一个序列a，要找到两个序列
a的下标为i,i+1,i+2, ….. i+k-1 当中的最小值为b[i];
c[i]就是最大值

题解:

单调队列，紫书中第八章的滑动窗口。。

优先队列也可做

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 #define MS(a) memset(a,0,sizeof(a))
 7 #define MP make_pair
 8 #define PB push_back
 9 const int INF = 0x3f3f3f3f;
10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
11 inline ll read(){
12     ll x=0,f=1;char ch=getchar();
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 //////////////////////////////////////////////////////////////////////////
18 const int maxn = 1e6+10;
19 
20 struct node{
21     int x,y;
22 }v[maxn];
23 
24 int n,k;
25 int a[maxn],mi[maxn],mx[maxn];
26 
27 void getmin(){
28     int head=1,tail=0;
29     for(int i=1; i<k; i++){
30         while(head<=tail && a[i]<=v[tail].x) tail--; 
31         tail++; v[tail].x=a[i],v[tail].y=i;
32     }
33     for(int i=k; i<=n; i++){
34         while(head<=tail && a[i]<=v[tail].x) tail--; // 插入到第一个比a[i]小的下一个位置，并把无用的【不可能出现在答案里的值，如果后面的一个位置比这个位置的值小，那么肯定要小的】删除
35         tail++; v[tail].x=a[i],v[tail].y=i;
36         while(head<=tail && i-k+1>v[head].y) head++; // 删除队首，已经不再这个窗口里的元素
37         mi[i-k+1] = v[head].x;
38     }
39 }
40 
41 void getmax(){
42     int head=1,tail=0;
43     for(int i=1; i<k; i++){
44         while(head<=tail && a[i]>=v[tail].x) tail--;
45         tail++; v[tail].x=a[i],v[tail].y=i;
46     }
47     for(int i=k; i<=n; i++){
48         while(head<=tail && a[i]>=v[tail].x) tail--;
49         tail++; v[tail].x=a[i],v[tail].y=i;
50         while(head<=tail && i-k+1>v[head].y) head++;
51         mx[i-k+1] = v[head].x;
52     }
53 }
54 
55 int main(){
56     cin >> n >> k;
57     for(int i=1; i<=n; i++)
58         a[i] = read();
59     getmin();
60     getmax();
61 
62     cout << mi[1];
63     for(int i=2; i<=(n-k+1); i++)
64         cout << " " << mi[i];
65     cout << endl;
66 
67     cout << mx[1];
68     for(int i=2; i<=(n-k+1); i++)
69         cout << " " << mx[i];
70     cout << endl;
71 
72     return 0;
73 }

优先队列的写法

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <vector>
 6 using namespace std;
 7 typedef long long ll;
 8 #define MS(a) memset(a,0,sizeof(a))
 9 #define MP make_pair
10 #define PB push_back
11 const int INF = 0x3f3f3f3f;
12 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
13 inline ll read(){
14     ll x=0,f=1;char ch=getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
16     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 //////////////////////////////////////////////////////////////////////////
20 const int maxn = 1e6+10;
21 
22 int a[maxn],mi[maxn],mx[maxn];
23 
24 struct node1{
25     int i;
26     bool operator<(const node1& rhs) const{
27         return a[i]>a[rhs.i];
28     }
29 };
30 
31 struct node2{
32     int i;
33     bool operator<(const node2& rhs) const{
34         return a[i]<a[rhs.i];
35     }
36 };
37 
38 priority_queue<node1> q1;
39 priority_queue<node2> q2;
40 
41 int main(){
42     int n,k;
43     scanf("%d%d",&n,&k);
44     for(int i=1; i<=n; i++)
45         a[i] = read();
46     for(int i=1; i<k; i++){
47         q1.push(node1{i});
48         q2.push(node2{i});
49     }
50 
51     int cnt1=0,cnt2=0;
52 
53     for(int i=k; i<=n; i++){
54         q1.push(node1{i});
55         q2.push(node2{i});
56 
57         while(i-q1.top().i >= k) q1.pop();
58         mi[cnt1++] = a[q1.top().i];
59 
60         while(i-q2.top().i >= k) q2.pop();
61         mx[cnt2++] = a[q2.top().i];
62     }
63 
64     for(int i=0; i<cnt1; i++){
65         cout << mi[i];
66         if(i==cnt1-1) cout << endl;
67         else cout << " ";
68     }
69 
70     for(int i=0; i<cnt2; i++){
71         cout << mx[i];
72         if(i==cnt2-1) cout << endl;
73         else cout << " ";
74     }
75 
76     return 0;
77 }