首页 > 代码库 > monkey king

monkey king

2024-07-31 18:45:05   220人阅读

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

32 11 23 330 11 00 040 01 00 11 10

Sample Output

121
题目大意：坐标（x0，y0）不存在任意（x，y）使得==》x>x0&&y>y0，则他为KING，记录KING的个数；

代码1（Time Limit Exceeded）：
 1 #include<stdio.h> 2 struct position //记录猴子的位置 3 { 4     int x,y; 5 }moky[50010]; 6 int main() 7 { 8     int N; 9     while(scanf("%d",&N)!=EOF){10         if(N==0)11             break;12         int i,king=0,j,flag_x,flag_y;13         for(i=0;i<N;i++)14             scanf("%d%d",&moky[i].x,&moky[i].y);15         for(i=0;i<N;i++){16             for(j=0;j<N;j++){17                 if(i==j)18                     continue;19                 flag_x=1,flag_y=1;//标记猴子坐标是否满足要求20                 if(moky[i].x<=moky[j].x)21                     flag_x=0;22                 if(moky[i].y<=moky[j].y)23                     flag_y=0;24                 if(flag_x==0&&flag_y==0)25                     break;26             }27             if(flag_x==1||flag_y==1)//若没有同时大于等于它的坐标就可以为KING28                 king++;29         }30         printf("%d\n",king);31     }32     return 0;33 }

实验数据截图：

 

源代码2:（Wrong answer）：

 

 

 

#include<stdio.h>#include<algorithm>using namespace std;struct monkey //记录猴子的坐标{    int x,y;}moky[50000];bool cmp(monkey a,monkey b)//对猴子坐标排序{    if(a.x!=b.x)        return a.x>b.x;    return a.y>b.y;}int comp(monkey a,monkey b)//判断是否满足猴子王的条件{    if(a.x>=b.x&&a.y>=b.y)        return 0;    else        return 1;}int main(){    int N;    while(scanf("%d",&N)!=EOF){        if(N==0)            return 0;        int i,king=0;        for(i=0;i<N;i++)            scanf("%d%d",&moky[i].x,&moky[i].y);        sort(moky,moky+N,cmp);//对猴子坐标排序        for(i=0;i<N;i++){            if(i==0)                king++;            else if(comp(moky[0],moky[i])==1)//判断是否满足猴子王的要求                king++;            else                break;        }        printf("%d\n",king);    }    return 0;}

测试数据截屏：

monkey king


联系
我们