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

POJ 2419 Forests [解题报告] Java

Forests

问题描述 :

If a tree falls in the forest, and there’s nobody there to hear, does it make a sound? This classic conundrum was coined by George Berkeley (1685-1753), the Bishop and influential Irish philosopher whose primary philosophical achievement is the advancement of what has come to be called subjective idealism. He wrote a number of works, of which the most widely-read are Treatise Concerning the Principles of Human Knowledge (1710) and Three Dialogues between Hylas and Philonous (1713) (Philonous, the “lover of the mind,” representing Berkeley himself).

输入:

A forest contains T trees numbered from 1 to T and P people numbered from 1 to P. Standard input consists of a line containing P and T followed by several lines, containing a pair of integers i and j, indicating that person i has heard tree j fall.

输出:

People may have different opinions as to which trees, according to Berkeley, have made a sound. Output how many different opinions are represented in the input? Two people hold the same opinion only if they hear exactly the same set of trees. You may assume that P < 100 and T < 100.

样例输入:

3 4
1 2
3 3
1 3
2 2
3 2
2 4

样例输出:

2

解题代码:

//* @author: 82638882@163.com
import java.io.*;
import java.util.Arrays;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  String[] ss=in.readLine().split(" ");
  int a=Integer.parseInt(ss[0]);
  int b=Integer.parseInt(ss[1]);
  boolean[][] p=new boolean[a][b];
  my[] p2=new my[a];
  for(int i=0;i< a;i++)
    p2[i]=new my();
  while(in.ready())
   {
    ss=in.readLine().split(" ");
    int x=Integer.parseInt(ss[0]);
    int y=Integer.parseInt(ss[1]);
    p[x-1][y-1]=true;
   }
  for(int i=0;i< a;i++)
    for(int j=0;j< b;j++)
	if(p[i][j]){
	  p2[i].cnt++;
	  p2[i].n+=(j+1)*(j+1)*(j+1)*(j+1);
	}
				
  Arrays.sort(p2);
  int sum=1;
  for(int i=1;i< a;i++)
  {
   if(p2[i].n==p2[i-1].n&&p2[i].cnt==p2[i-1].cnt) continue;
   sum++;
  }
  System.out.println(sum);
 }
}

class my implements Comparable< my>
{
    int n=0,cnt=0;

    public int compareTo(my o) {
	 if(cnt==o.cnt)
	 return n-o.n;
	 return cnt-o.cnt;
    }
}

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

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.