首页 > 专题系列 > Java解POJ > POJ 2726 Holiday Hotel [解题报告] Java
2013
11-11

POJ 2726 Holiday Hotel [解题报告] Java

Holiday Hotel

问题描述 :

Mr. and Mrs. Smith are going to the seaside for their holiday. Before they start off, they need to choose a hotel. They got a list of hotels from the Internet, and want to choose some candidate hotels which are cheap and close to the seashore. A candidate hotel M meets two requirements:
  1. Any hotel which is closer to the seashore than M will be more expensive than M.
  2. Any hotel which is cheaper than M will be farther away from the seashore than M.

输入:

There are several test cases. The first line of each test case is an integer N (1 <= N <= 10000), which is the number of hotels. Each of the following N lines describes a hotel, containing two integers D and C (1 <= D, C <= 10000). D means the distance from the hotel to the seashore, and C means the cost of staying in the hotel. You can assume that there are no two hotels with the same D and C. A test case with N = 0 ends the input, and should not be processed.

输出:

For each test case, you should output one line containing an integer, which is the number of all the candidate hotels.

样例输入:

5
300 100
100 300
400 200
200 400
100 500
0

样例输出:

2

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.Arrays;
class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
  {
    int a=Integer.parseInt(in.readLine());
    if(a==0) break;
    my[] p=new my[a];
    for(int i=0;i< a;i++)
    {
	String[] ss=in.readLine().split(" ");
	p[i]=new my(Integer.parseInt(ss[0]),Integer.parseInt(ss[1]));
    }
    Arrays.sort(p);
    int cnt=0;
    for(int i=1,n=0;i< a;i++)
    {
	if(p[n].a==p[i].a){
		cnt++;
		n=i;
	}
	else if(p[n].b<=p[i].b) cnt++;
	else n=i;
     }
     System.out.println(a-cnt);
    }
  }	
}
class my implements Comparable< my>
{
	int a,b;
	public my(int x,int y)
	{
		a=x;
		b=y;
	}
	public int compareTo(my o) {
		if(a==o.a)return o.b-b;
		return a-o.a;
	}
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?