POJ2823 滑动窗口（单调队列）

来学习一下单调队列：

他只可以从队尾入队，但可以从队尾或队首出队，来维护队列的单调性。单调队列有两种单调性：元素的值单调和元素的下标单调。

单调队列可以用来优化DP。状态转移方程形如dp[i]=min{dp[j]+f[j]},i-a<=j<=i-b。i增加1，j的上下界都增加1，即加入一个新的决策到候选集中，要把过时的决策剔除。当决策的取值范围的上下界均单调变化时，每个决策在候选集合中插入或删除最多一次，我们就可以用单调队列来优化。

回到这个题目：

用Min[i]和Max[i]表示以i结尾的大小为k的窗口中的最值。

以Min[i]为例，Min[i]=min{aj} ,i-k+1<=j<=i; i加1，j的上下界同时加1。Min用单调递增的队列维护。

（1）单调递增的队列，队头元素最小；

（2）待入队的元素<=队尾元素，队尾元素出队，直到满足单调性或队列为空，将此元素入队；

（3）队头元素下标<i-k+1,说明过时了，要删去。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define MAXN 1000010

 4 int a[MAXN],Min[MAXN],Max[MAXN],Q[MAXN],n,k;

 5

 6 void get_min(){//求最小

 7     int st=0,ed=0;

 8     Q[ed++]=1;

 9     Min[1]=a[1];

10     for(int i=2;i<=n;i++){

11         while(st<ed&&a[i]<a[Q[ed-1]]) ed--;//删除队尾元素

12         Q[ed++]=i;//插入队尾元素

13         while(st<ed&&Q[st]<i-k+1) st++;//删除队首过时元素

14         Min[i]=a[Q[st]];//此时答案就是队首元素

15     }

16 }

17

18 void get_max(){//求最大

19     int st=0,ed=0;

20     Q[ed++]=1;

21     Max[1]=a[1];

22     for(int i=2;i<=n;i++){

23         while(st<ed&&a[i]>a[Q[ed-1]]) ed--;

24         Q[ed++]=i;

25         while(st<ed&&Q[st]<i-k+1) st++;

26         Max[i]=a[Q[st]];

27     }

28 }

29

30 int main(){

31     scanf("%d%d",&n,&k);

32     for(int i=1;i<=n;i++) scanf("%d",&a[i]);

33     get_min();get_max();

34     for(int i=k;i<n;i++) cout<<Min[i]<<" "; cout<<Min[n]<<endl;

35     for(int i=k;i<n;i++) cout<<Max[i]<<" "; cout<<Max[n]<<endl;

36     return 0;

37 }

巴特西

POJ2823 滑动窗口（单调队列）

最新文章

热门文章

巴特西

POJ2823 滑动窗口 （单调队列）

最新文章

热门文章

POJ2823 滑动窗口（单调队列）