当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

线段树练习POJ 3264

发表于: 2012-12-03   作者:128kj   来源:转载   浏览:
摘要: 问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分别求出这些区间中最高和最矮的差值。   Sample Input 6 3  (六只奶牛,下面分别是它们的身高,3个区间) 1 7 3 4 2 5 1 5 4 6 2 2 Sample Output 6 3 0 import java.io.StreamTokeniz
问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分别求出这些区间中最高和最矮的差值。

  Sample Input

6 3  (六只奶牛,下面分别是它们的身高,3个区间)
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output

6
3
0

import java.io.StreamTokenizer;   
import java.io.BufferedReader;   
import java.io.InputStreamReader;   
import java.io.PrintWriter;   
import java.io.OutputStreamWriter;   
import java.io.IOException;   

class tree{  //线段树节点
    int left,right,maxvalue,minvalue;  
   }

public class Main{
     tree[] tt;//线段树,用数组实现
  
    int height[];//奶牛身高

    public Main(int[] height){
      this.height=height;
      tt=new tree[131070];
      for(int i=0;i<131070;i++)
       //数组大小的计算参看:http://128kj.iteye.com/blog/1739064
         tt[i]=new tree();
    }

    private void built_tree(int lp,int rp,int pos){  //构建以pos为根的线段树
      tt[pos].left=lp;  
      tt[pos].right=rp;  
      if(lp==rp){  
        tt[pos].maxvalue=height[rp];  
        tt[pos].minvalue=height[lp];  
        return ;  
    }  
    int mid=(tt[pos].left+tt[pos].right)>>1;  
    built_tree(lp,mid,pos<<1);  
    built_tree(mid+1,rp,pos<<1|1);  
    tt[pos].maxvalue=Math.max(tt[pos<<1].maxvalue,tt[pos<<1|1].maxvalue);  
    tt[pos].minvalue=Math.min(tt[pos<<1].minvalue,tt[pos<<1|1].minvalue);  
  }  

   //找[lp,rp]上的最大值
   private int findmax(int lp,int rp,int pos){  
    if(tt[pos].left==lp&&tt[pos].right==rp){  
        return tt[pos].maxvalue;  
    }  

    int mid=(tt[pos].left+tt[pos].right)>>1;  
    if(rp<=mid){  
      return findmax(lp,rp,pos<<1);  
    }  
    else if(lp>mid)  
        return findmax(lp,rp,pos<<1|1);  
    else{  
      return Math.max( findmax(lp,mid,pos<<1), findmax(mid+1,rp,pos<<1|1));  
    }  
  }  

 //找[lp,rp]上的最小值
  private int findmin(int lp,int rp,int pos){  
    if(tt[pos].left==lp&&tt[pos].right==rp){  
        return tt[pos].minvalue;  
    }  
    int mid=(tt[pos].left+tt[pos].right)>>1;  
    if(rp<=mid)  
        return findmin(lp,rp,pos<<1);  
    else if(lp>mid)  
        return findmin(lp,rp,pos<<1|1);  
    else  
        return Math.min( findmin( lp,mid,pos<<1 ),findmin( mid+1,rp,pos<<1|1 ) );  
}  

   public static void  main(String args[]) throws IOException{  
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(   
      new InputStreamReader(System.in)));   
      PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));   

    while(st.nextToken() != StreamTokenizer.TT_EOF) { 

      int n=(int) st.nval;    
       st.nextToken();
      int q=(int) st.nval;
      int[] height=new int[n+1];  
      for(int i=1;i<=n;++i){
           st.nextToken();
          height[i]=(int) st.nval;    
      }

      Main ma=new Main(height);  
      ma.built_tree(1,n,1);  
      int x,y;  
      while(q-->0){  
        st.nextToken();
        x=(int) st.nval; 
        st.nextToken();
        y=(int) st.nval;
        int mmax=ma.findmax(x,y,1);  
        int mmin=ma.findmin(x,y,1);  
        System.out.printf("%d\n",mmax-mmin);  
      }  
      out.flush();      

    }  
  }
}  

线段树练习POJ 3264

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Mayor's posters Description The citizens of Bytetown, AB, could not stand that the candidates
题意就是让求在某个点左面的星星的个数。因为y是按升序输入的,所以只需要考虑x即可。此题可以用树
Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26354 Accepted: 11498 Descri
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 9712 Accepted: 4679 De
Mayor's posters Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 34272 Accepted: 99
分类: 线段树 2013-07-26 11:37 297人阅读 评论(1) 收藏 举报 离散化: 将所有的x轴坐标存在一个数
一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象
点我看题目链接 题意 : 很多花盆组成的圆圈,每个花盆都有一个值,给你两个数a,b代表a位置原来的
http://poj.org/problem?id=2828 一开始敲了个splay,直接模拟。 tle了。。 常数太大。。 好吧,说
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 13017 Accepted: 6449 D
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号