2013
11-10

Monkeys’ Pride

Background

There are a lot of monkeys in a mountain. Every one wants to be the monkey king. They keep arguing with each other about that for many years. It is your task to help them solve this problem.

Problem

Monkeys live in different places of the mountain. Let a point (x, y) in the X-Y plane denote the location where a monkey lives. There are no two monkeys living at the same point. If a monkey lives at the point (x0, y0), he can be the king only if there is no monkey living at such point (x, y) that x>=x0 and y>=y0. For example, there are three monkeys in the mountain: (2, 1), (1, 2), (3, 3). Only the monkey that lives at the point (3,3) can be the king. In most cases, there are a lot of possible kings. Your task is to find out all of them.

The input consists of several test cases. In the first line of each test case, there are one positive integers N (1<=N<=50000), indicating the number of monkeys in the mountain. Then there are N pairs of integers in the following N lines indicating the locations of N monkeys, one pair per line. Two integers are separated by one blank. In a point (x, y), the values of x and y both lie in the range of signed 32-bit integer. The test case starting with one zero is the final test case and has no output.

For each test case, print your answer, the total number of the monkeys that can be possible the king, in one line without any redundant spaces.

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


1
2
1


//* @author: ccQ.SuperSupper
import java.util.*;	//Monkeys' Pride

class node implements Comparable {
int x,y;
public int compareTo(Object o) {
node oo=(node)o;
if(this.x!=((node)o).x)
return this.x>((node)o).x?1:0;
return this.y>((node)o).y?1:0;
}
}
public class Main{

static int N = 500000+100;

public static void main(String []args) throws Exception{
int i,y,n,ans;
node mokey[] = new node[N];
for(i=0;i< N;++i)
mokey[i] = new node();
Scanner cin = new Scanner(System.in);

while(cin.hasNext()){
n = cin.nextInt();
if(n==0) break;
for(i=0;i< n;++i){
mokey[i].x = cin.nextInt();
mokey[i].y = cin.nextInt();
}
Arrays.sort(mokey,0,n);
ans = 1; y = mokey[n-1].y;

for(i=n-2;i>=0;--i){
if(y< mokey[i].y){
++ans;
y = mokey[i].y;
}
}
System.out.println(ans);
}
}
}

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

3. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!