首页 > 代码库 > HDU 3264 区间内的最大最小之差

HDU 3264 区间内的最大最小之差

2024-07-14 23:53:27   219人阅读

题目链接：http://poj.org/problem?id=3264

题目大意：
在给定一堆牛的数量以及其高度的时候，每次给定一段区间，求这个区间内最高的牛和最矮的牛的高度之差为多少。

 

这道题目用线段树能快速的求解，因为此处不涉及更新，所以无需写update函数

不同于之前只定义一个tree数组，这回我们需要定义一个Max和一个Min数组分别子弟想存放较大和较小值

通过query找到区间内的最大值q，和最小值p，那么q-p便是我们所求的

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 #define N 50005 8 #define INF 0x3f3f3f3f 9 10 int height[N],Min[4*N],Max[4*N],D;11 12 int query(int a,int b)13 {14     int i=D+a-1,j=b+D+1;15     int p=INF,q=0;16     //if(a==b){return 0;}17     for(;i^j^1;i>>=1,j>>=1){18         if(~i&1){19             p=min(p,Min[i^1]);20             q=max(q,Max[i^1]);21         }22         if(j&1){23             p=min(p,Min[j^1]);24             q=max(q,Max[j^1]);25         }26     }27     return q-p;28 }29 int main()30 {31     int n,Q,a,b;32     while(scanf("%d%d",&n,&Q)!=EOF){33         memset(Min,0,sizeof(Min));34         memset(Max,0x3f,sizeof(Max));35         for(D=1;D<n+2;D<<=1);36         for(int i=1;i<=n;i++){37             scanf("%d",&height[i]);38             Min[D+i]=Max[D+i]=height[i];39         }40         for(int i=D-1;i>=1;i--){41             Min[i]=min(Min[i<<1],Min[i<<1|1]);42             Max[i]=max(Max[i<<1],Max[i<<1|1]);43         }44         for(int i=1;i<=Q;i++){45             scanf("%d%d",&a,&b);46             printf("%d\n",query(a,b));47         }48     }49     return 0;50 }

 


联系
我们