POJ 1828 Monkeys'Pride(이 TLE 제목)-from lanshui_Yang
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C에서 파일 입/출력저장 및 , 우리는 파일 유형을 가리키는 구조 포인터를 사용합니다 - FILE. fopen() 함수는 기존 파일을 열거나 새 파일을 만드는 데 사용됩니다. 여기서 fp는 열린(또는 생성된) 파일에 대한 참조를 보유할...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.