字节跳动测试开发第一题_字节跳动测试数据库

时间限制：1秒

空间限制：32768K

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x
的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0,
1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

输入描述:

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。 对于 50%的数据, 1 <= N <=
10000; 对于 100%的数据, 1 <= N <= 500000;

输出描述:

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

输入例子1:

5 1 2 5 3 4 6 7 5 9 0

输出例子1:

4 6 7 5 9 0

按照y从大到小排序，然后x从小到大选择，x值比前一个大的y值肯定比前一个大（y从大到小排列），从而是“最大的”点

#include <iostream>
#include <list>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
    int x;
    int y;
};
bool cmp(node n1,node n2)
{
    return n1.y>n2.y;
}
node nod[1000000];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&nod[i].x,&nod[i].y);
        }
        sort(nod,nod+n,cmp);
        int min=-1;
        for(int i=0;i<n;i++)
        {
            if(nod[i].x>min)
            {
                min=nod[i].x;
                printf("%d %d\n",nod[i].x,nod[i].y);
            }
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

转载自牛客网https://www.nowcoder.com/test/question/done?tid=22147657&qid=141067