首页 > 专题系列 > Java解POJ > POJ 2481 Cows [解题报告] Java
2013
11-11

POJ 2481 Cows [解题报告] Java

Cows

问题描述 :

Farmer John’s cows have discovered that the clover growing along the ridge of the hill (which we can think of as a one-dimensional number line) in his field is particularly good.

Farmer John has N cows (we number the cows from 1 to N). Each of Farmer John’s N cows has a range of clover that she particularly likes (these ranges might overlap). The ranges are defined by a closed interval [S,E].

But some cows are strong and some are weak. Given two cows: cowi and cowj, their favourite clover range is [Si, Ei] and [Sj, Ej]. If Si <= Sj and Ej <= Ei and Ei - Si > Ej – Sj, we say that cowi is stronger than cowj.

For each cow, how many cows are stronger than her? Farmer John needs your help!

输入:

The input contains multiple test cases.

For each test case, the first line is an integer N (1 <= N <= 105), which is the number of cows. Then come N lines, the i-th of which contains two integers: S and E(0 <= S < E <= 105) specifying the start end location respectively of a range preferred by some cow. Locations are given as distance from the start of the ridge.

The end of the input contains a single 0.

输出:

For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of cows that are stronger than cowi.

样例输入:

3
1 2
0 3
3 4
0

样例输出:

1 0 0

温馨提示:

Huge input and output,scanf and printf is recommended.

解题代码:

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[];
   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();
    }
  }
}

  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  4. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  5. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥