2013
11-11

# 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]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
import java.io.*;
import java.util.Arrays;
class Main
{
public static void main(String[] args) throws IOException
{
while(true)
{
if(a==0) break;
my[] p=new my[a];
for(int i=0;i< a;i++)
{
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. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？