BUPT2017 wintertraining(16) #5 D

POJ - 2823

题意

给定n，k，求滑窗[i,i+k-1]在(1<=i<=n)的最大值最小值。

题解

单调队列或堆。

入队的条件是当前的进入了滑窗范围。

出队的条件是当前不在滑窗范围。

代码

我用堆写的，但是堆写错了个小地方，查了很久才发现。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define pii pair<int,int>

#define mp(i,j) make_pair(i,j)

#define N 1000006

using namespace std;

int n,k;

int a[N];

pii q[N];

int back;

void push(pii a,int d){

	q[++back]=a;

	for(int i=back;i>1&&(d?q[i]>q[i>>1]:q[i]<q[i>>1]);i>>=1)

		swap(q[i],q[i>>1]);

}

void pop(int d){

	swap(q[1],q[back--]);

	for(int i=1;i<=(back>>1);){

		if(d?q[i]>=max(q[i<<1],q[i<<1|1]):q[i]<=min(q[i<<1],q[i<<1|1]))return;//qaq

		if(((i<<1|1)>back)||(d?q[i<<1]>q[i<<1|1]:q[i<<1]<q[i<<1|1])){

			swap(q[i<<1],q[i]);

			i<<=1;

		}else{

			swap(q[i<<1|1],q[i]);

			i=(i<<1|1);

		}

	}

}

int main() {

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

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		if(i<=k)push(mp(a[i],i),0);

	}

	for(int i=k;i<=n;i++){

		printf("%d ",q[1].first);

		while(back&&q[1].second<=i-k+1)pop(0);

		push(mp(a[i+1],i+1),0);

	}

	puts("");

	back=0;

	for(int i=1;i<=k;i++)push(mp(a[i],i),1);

	for(int i=k;i<=n;i++){

		printf("%d ",q[1].first);

		while(back&&q[1].second<=i-k+1)pop(1);

		push(mp(a[i+1],i+1),1);

	}

	return 0;

}

单调队列,写起来简单多了，而且也不会和手写堆一样容易出错。

#include <cstdio>

#define N 1000006

using namespace std;

int n,k;

int a[N],b[N],q[N],head,tail;

int main() {

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

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=n;i++){

		while(head<tail&&a[i]<q[tail-1])tail--;

		b[tail]=i;

		q[tail++]=a[i];

		while(head<tail&&b[head]<i-k+1)head++;

		if(i>=k)printf("%d ",q[head]);

	}

	puts("");

	tail=head=0;

	for(int i=1;i<=n;i++){

		while(head<tail&&a[i]>q[tail-1])tail--;

		b[tail]=i;

		q[tail++]=a[i];

		while(head<tail&&b[head]<i-k+1)head++;

		if(i>=k)printf("%d ",q[head]);

	}

	return 0;

}