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

树状数组练习:POJ 2481(JAVA)

发表于: 2012-12-08   作者:128kj   来源:转载   浏览:
摘要: 关于树状数组,请参考: http://128kj.iteye.com/blog/1743633 POJ 2481题意:    有n头牛(编号为1~n),每一头牛都有一个吃草区间[S, E],如果对于牛i和牛j来说,它们的吃草区间满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj
关于树状数组,请参考: http://128kj.iteye.com/blog/1743633

POJ 2481题意:
   有n头牛(编号为1~n),每一头牛都有一个吃草区间[S, E],如果对于牛i和牛j来说,它们的吃草区间满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的吃草区间,要求输出每头牛有几头牛比其强壮。
其中:1 <= N <= 100000, 0 <= S < E <= 100000

样例:

Sample Input

3          (3头牛)
1   2      牛的[s,e]值
0   3
3   4
0

Sample Output

1 0 0   (比第一头牛强的有一头,比第二头牛强的没有,比第三头牛强的没有)

分析:
  建一个全0的树状数组,然后将牛一个一个插入树状数组,当然必须先对e按照降序排列,每加入一只牛,当前已经加入树状数组的牛的s如果比这只牛小,那么那些牛就更强壮,所以这是在树状数组里的求和问题,只要求出在插入s之前已插入了多少头牛(求和)。另外,由于排序后,顺序和开始给出数据时的顺序不同,所以需要记录一下开始给出数据时的顺序。

下面是AC过的代码:
import java.io.StreamTokenizer;   
import java.io.BufferedReader;   
import java.io.InputStreamReader;   
import java.io.PrintWriter;   
import java.io.OutputStreamWriter;   
import java.io.IOException;   
import java.util.Arrays;

   class TNode implements Comparable{//表示一头牛
    int s;//牛吃草的左端点
    int e;//右端点
    int label;//牛的序号
    public int compareTo(Object o) {  
       int v=((TNode)o).e;
       if(this.e!=v) //按右端点降序排列
         return v-this.e;   
       return this.s-((TNode)o).s;//右端点相等,按左端点升序排序
    }

    public String toString(){
        return ("["+s+","+e+"]");
    }
  }

 public class Main{//
   static  int N=100015;
   TNode[] cow;
   int cal[];//树状数组
   int res[];//res[i]表示比牛i强壮的牛的个数
   int maxn;//右端点的最大值

  public Main(){
    
     }
       
   private int lowbit(int t){//计算cal[t]展开的项数   
   return t&(-t);   
  }   

  private int Sum(int k){ //求前k项的和.   
   int sum=0;    
    while(k>0){    
       sum+=cal[k];    
       k=k-lowbit(k);    
    }        
    return sum;    
  }    

  private void update(int i,int x){ //增加某个元素的大小,给某个节点 i 加上 x   
      while(i<=maxn){    
        cal[i]=cal[i]+x; //更新父节点
        i=i+lowbit(i);    
     }    
    }    

  
   

  public static void  main(String args[]) throws IOException{
        Main ma=new Main();
        ma.go();
   }

    public void go() throws IOException{
     
      StreamTokenizer st = new StreamTokenizer(new BufferedReader(      
      new InputStreamReader(System.in)));      
      PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));      

      while(true) {
       st.nextToken();      
      int n= (int) st.nval;    //牛的个数  
      if(n==0) break;

     cow=new TNode[N];
     cal=new int[N];
     res=new int[N];
     for(int i=0;i<N;i++){
       cow[i]=new TNode();
      // cal[i]=0;
      }
      for(int i=0;i<n;i++) {//读入牛的吃草区间
            st.nextToken();     
           cow[i].s=(int) st.nval;
             st.nextToken();     
           cow[i].e=(int) st.nval;
           cow[i].s++; 
           cow[i].e++;
           cow[i].label=i;//牛的原始序号
           if(cow[i].e>maxn) maxn=cow[i].e;//最大右端点
      }
       
        Arrays.sort(cow);//排序

     // for(int i=0;i<n;i++)
       // System.out.println(cow[i]);
 
      for(int i=0;i<n;i++) {
           if(i!=0&&cow[i].s==cow[i-1].s&&cow[i].e==cow[i-1].e)//两头牛有相同的吃草区间
                res[cow[i].label]=res[cow[i-1].label];//它们有相同的答案
            else res[cow[i].label]=Sum(cow[i].s);//统计比cow[i].label这头牛强的牛的数目
            update(cow[i].s,1);//更新
        }
        System.out.printf("%d",res[0]);
        for(int i=1;i<n;i++) System.out.printf(" %d",res[i]);
        System.out.println();
    }
  }
} 

树状数组练习:POJ 2481(JAVA)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
关于树状数组,参看: http://128kj.iteye.com/blog/1743633 POJ3067题意: 东海岸与西海岸分别有N和M
关于树状数组:参看: http://128kj.iteye.com/blog/1743633 POJ3321 题意: 一棵具有n个节点的树,
接前文:二维树状数组学习之一:彻底理解 http://128kj.iteye.com/blog/1746732 POJ1195题意:大概题
这道题好像被贱做了,看起来像二维的树状数组,其实只是一维的,可能是数据太大了,矩阵开不那么大
  这题是我看了大白书树状数组后刷的第一道题,确实难度不小,所以只好上网找题解了,网上的做法
  之前说过这是线段树的裸题,但是当看了http://kenby.iteye.com/blog/962159 这篇题解后我简直震
题目来源Ural Collegiate Programming Contest 1999 poj上的链接点这儿(这个是难得的1Y"o((>ω&
Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20885 Accepted: 9097 Descrip
【POJ 1195】 Mobile phones (树状数组) Mobile phones Time Limit: 5000MS Memory Limit: 65536K T
一个水题。。。结果因为一个加号写成了减号。。。硬是耗费了一个多小时。。。T^T Counting Black Ti
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号