首页 > 其他 > 详细

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

时间:2014-07-31 09:47:16      阅读:365      评论:0      收藏:0      [点我收藏+]

题目链接: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 }

 

HDU 3264 区间内的最大最小之差,布布扣,bubuko.com

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

原文:http://www.cnblogs.com/CSU3901130321/p/3879918.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!