[POJ2823][洛谷P1886]滑动窗口 Sliding Window

题目大意：有一列数，和一个窗口，一次能框连续的s个数，初始时窗口在左端，不断往右移动，移到最右端为止，求每次被框住的s个数中的最小数和最大数。

解题思路：这道题是一道区间查询问题，可以用线段树做。每个节点保存最大值和最小值即可。

注意点：①当s=1时可直接输出，否则会很慢；②查询操作不要返回值，我当时直接返回了struct，导致洛谷上TLE；③POJ上用C++提交，G++会TLE。

C++ Code：

#include<cstdio>

#include<cctype>

#define max(a,b) (((a)>(b))?(a):(b))

#define min(a,b) (((a)<(b))?(a):(b))

struct node{

	int Max,Min;

	node(int a=-1000000000,int b=1000000000):Max(a),Min(b){}

}d[4000401],ans[1000041];

int n,s,ansMax,ansMin;

inline int readint(){

	char c=getchar();

	bool b=false;

	while(!isdigit(c))b=c=='-',c=getchar();

	int p=0;

	while(isdigit(c))p=(p<<3)+(p<<1)+(c^'0'),c=getchar();

	return (b)?(-p):p;

}

void bt(int l,int r,int o){

	if(l==r){

		d[o].Max=d[o].Min=readint();

		return;

	}

	int mid=l+r>>1;

	bt(l,mid,o<<1);

	bt(mid+1,r,o<<1|1);

	d[o].Max=max(d[o<<1].Max,d[o<<1|1].Max);

	d[o].Min=min(d[o<<1].Min,d[o<<1|1].Min);

}

void query(int l,int r,int o,int L,int R){

	if(L<=l&&r<=R){

		ansMax=max(ansMax,d[o].Max);

		ansMin=min(ansMin,d[o].Min);

		return;

	}

	int mid=l+r>>1;

	if(L<=mid)query(l,mid,o<<1,L,R);

	if(mid<R)query(mid+1,r,o<<1|1,L,R);

}

int main(){

	n=readint(),s=readint();

	if(s==1){

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

			ans[i].Max=readint();

			printf("%d ",ans[i].Max);

		}

		printf("%d\n",ans[n].Max=readint());

		for(int i=1;i<n;++i)printf("%d ",ans[i].Max);

		printf("%d\n",ans[n].Max);

		return 0;

	}

	bt(1,n,1);

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

		ansMax=-1000000000,ansMin=1000000000;

		query(1,n,1,i-s+1,i);

		ans[i].Max=ansMax;

		ans[i].Min=ansMin;

	}

	for(int i=s;i<n;++i)printf("%d ",ans[i].Min);

	printf("%d\n",ans[n].Min);

	for(int i=s;i<n;++i)printf("%d ",ans[i].Max);

	printf("%d\n",ans[n].Max);

	return 0;

}

巴特西

[POJ2823][洛谷P1886]滑动窗口 Sliding Window

最新文章

热门文章