Description
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.
Input
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.
Output
Sample Input
3 2 1 1 2 3 3 3 0 1 1 0 0 0 4 0 0 1 0 0 1 1 1 0
Sample Output
1 2 1
题目大意很简单， 童话点 说就是 选猴王的故事 ：有 n 只猴子，他们 生活地点的坐标 用 (X,Y) 表示（任意两只猴子的 生活地点 的坐标 各不相同），假设一只猴子的 生活地点的坐标为 （X1,Y1），如果 其余的 猴子的 生活地点 的坐标 （Xn，Yn）均不满足（Xn >= X1 并且 Yn >= Y1),那么这只猴子 就能成为 猴王 ，题目 就是让求出 能够 成为猴王 的 猴子 的数目。
Ps: 题目看似简单 ，用常规思路解题的话 很容易 TLE，于是要 变换思路 使程序更高效~
具体详解请看代码:
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
struct point
{
int x;
int y;
} a[50005]; // 定义 猴子 的 数组 ~
bool cmp(point a,point b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
} // 把猴子数组 按 x 的值从小到大排序（如果 x 相同 ，就按 y 的值从小到大排序）
int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
if(n==0)
break;
int i,j;
for(i=0; i<n; i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a,a+n,cmp); // 把 猴子 数组排序
int maxX = a[n-1].x;
int maxY = a[n-1].y;
int sum = 1; // 注意 此处 把sum 初始化为 1，因为 排完序后 的 猴子a[n-1] 一定是 猴王 ！！
for(i=n-1;i>=0;i--) // 以下为 核心部分 ，请仔细 品味 ，相信不难看懂 ，
{ //否则 就亲自动手 模拟 一下 就 理解啦
if(a[i].x == maxX)
continue;
if(a[i].x < maxX)
{
maxX = a[i].x;
if(a[i].y > maxY)
{
sum++;
maxY = a[i].y;
}
}
}
printf("%d\n",sum);
}
return 0;
}