POJ 1828 Monkeys'Pride(이 TLE 제목)-from lanshui_Yang

Description
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. 
Input
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.
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.
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, Y)가 모두 만족하지 않는다(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
",sum); } return 0; }

좋은 웹페이지 즐겨찾기