现在的位置: 首页 > 综合 > 正文

poj 1828 Monkeys’ Pride

2017年10月18日 ⁄ 综合 ⁄ 共 765字 ⁄ 字号 评论关闭

题目大意:

题目给出n个点,求出有多少点满足没有横纵坐标同时大于等于这个点的个数。也就是在这所有的点中,这样的点有多少个?什么样的点呢?设这个点(x0,y0),那么如果不存在(x,y)使得x>=x0并且y>=y0,那么这就算一个点,求出所有这样的点。

 

题解:对于任意一点,以x轴为水平线,对这点来说,如果他要是king点(即题目要求的点),那么它的y必须比在它后面,也就是x比它大或者等于它的所有点的y都要大,而x比它小的点y比它大或小都无关紧要。那么这个点就是king点。

 

算法

1、排序(从大到小,从小到大都可以,根据x排,x相等按y排)

2、从x最大的点开始往最小的点遍历,用max存所能得到的最大y。

3、判断当前点的y是否大于max,大于则是一个king点。不是则继续下一个点,执行第3步,直到结束。

 

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

struct point {
    int x,y;
    bool operator < (const point &a)const {
        if (a.x == x) {
            return a.y > y;
        } else
            return a.x > x;
    }
} p[50005];

int main() {
    int n;
    while(~scanf("%d",&n) && n) {
        int num = 1;
        for(int i = 1 ; i <= n ; i++) {
            scanf("%d%d",&p[i].x,&p[i].y);
        }
        sort(p+1,p+n+1);
        int max = p[n].y;
        for(int i = n - 1 ; i > 0 ; i--) {
            if(p[i].y > max) {
                max = p[i].y;
                num++;
            }
        }
        printf("%d\n",num);
    }
    return 0;
}

 

抱歉!评论已关闭.