字节跳动——2018校招算法方向

字节跳动——2018校招算法方向

题目描述：
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
题解：
1，按照x坐标降序排序
2，初始化最大值为第一个点
3，循环遍历，比较当前y坐标是否大于最大值，若是，则更新坐标
4，定义栈保存最大值
5，使用scanf和printf输入输出，cin和cout会超时

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
typedef struct s{int x;int y;
}s;
bool cmp(s a, s b){return a.x > b.x;
}int main() {int n;scanf("%d", &n);s array[n+1], a;stack<s> sta;for(int i=0; i<n; i++){scanf("%d %d", &array[i].x, &array[i].y);}sort(array, array+n, cmp);a = {array[0].x, array[0].y};sta.push(a);for(int i=1; i<n; i++){if(array[i].x>a.x || array[i].y>a.y){a = {array[i].x, array[i].y};sta.push(a);}}while(!pty()){a = p();sta.pop();printf("%d %dn", a.x, a.y);}return 0;
}