本文主要是介绍POJ 2823 Sliding Window（线段树入门），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:
8 3 1 3 -1 -3 5 3 6 7一串数列，有一个窗口大小为3，从数列开始往后移动，输出最大和最小值。
-1 -3 -3 -3 3 3 3 3 5 5 6 7窗口大小为3
思路：
维护一个线段树，代码很详细
解题心得：
因为关键值的输入量有1000000，也就是叶节点有1000000个，总节点按理说是2000000-1，但这题得开3000000才能过
代码：
#include<stdio.h>
int max(int a,int b)
{return a>b?a:b;
}
int min(int a,int b)
{return a<b?a:b;
}struct Node
{int L,R;int maxn,minn;
};
Node Tree[3000000];//线段树
int a[1000001];//存输入数据
int ans_max[1000001],ans_min[1000001];//存输出数据//建树，节点为Tree[root],线段范围为l到r
void Maketree(int root,int l,int r)
{//1.给线段范围赋值Tree[root].L=l;Tree[root].R=r;//2.判断是否已经到达叶节点，若是则赋关键值并返回，否则继续延伸if(l==r){Tree[root].maxn=Tree[root].minn=a[l];//关键值即为题目要维护的元素。曾错在此处return;}else{//取要分割线段的中点int mid=(l+r)>>1;//建立左儿子Maketree(root*2,l,mid);//建立右儿子Maketree(root*2+1,mid+1,r);//根据左儿子与右儿子的关键值，更新自身关键值Tree[root].maxn=max(Tree[root*2].maxn,Tree[root*2+1].maxn);Tree[root].minn=min(Tree[root*2].minn,Tree[root*2+1].minn);return;}
}//寻找以root为根中，范围为l到r的线段的关键值，结果存在maxn与minn中
void find(int root,int l,int r,int& maxn,int& minn)
{//如果树根的线段正好满足，存结果并返回,否则往下搜索if(Tree[root].L==l&&Tree[root].R==r){maxn=Tree[root].maxn;minn=Tree[root].minn;return;}else{//取该树根线段的中点int mid=(Tree[root].L+Tree[root].R)>>1;//如果要查找的线段在树根线段中点左侧 T->L---l----r----mid--------T->Rif(mid>=r){//往左儿子寻找find(root*2,l,r,maxn,minn);}//如果要查找的线段在树根中点右侧else if(mid<l){//往右儿子寻找find(root*2+1,l,r,maxn,minn);}//如果要查找的线段在树根的左儿子和右儿子中各占一部分else{//将要查找的线段分为两部分，一部分往左儿子找，一部分往右儿子找int max1,max2,min1,min2;//存放两边各自找到的关键值，取最优//左儿子部分find(root*2,l,mid,max1,min1);//右儿子部分find(root*2+1,mid+1,r,max2,min2);//取最优更新在此树根找到的结果maxn=max(max1,max2);minn=min(min1,min2);}return;}
}int main()
{int n,k;while(~scanf("%d%d",&n,&k)){int i;for(i=1;i<=n;i++){scanf("%d",&a[i]);}Maketree(1,1,n);for(i=1;i<=n-k+1;i++){find(1,i,i+k-1,ans_max[i],ans_min[i]);}for(i=1;i<=n-k+1;i++){if(i==1) printf("%d",ans_min[i]);else printf(" %d",ans_min[i]);}printf("\n");for(i=1;i<=n-k+1;i++){if(i==1) printf("%d",ans_max[i]);else printf(" %d",ans_max[i]);}printf("\n");}return 0;
} 这篇关于POJ 2823 Sliding Window（线段树入门）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
