牛客小白月赛20 H.好点

题目链接

题目描述

在一个二维平面里，如果一个点 s 的右上方没有点，即不存在 (x,y) 同时满足 x>=xs，y>=ys这两个条件，Keven 认为这个点是“最好的点“。
现在 Keven 给你 n 个点，他希望你能够找出所有“最好的点“，并按照横坐标大小从小到大输出。

输入描述

第一行一个整数 n ，表示点的数量（1<=n<=5e5）
接下来 n 行，每行两个整数 xi,yi，表示一个点的坐标。（-1e9<=x,y<=1e9）
输入保证不存在横坐标相等或纵坐标相等的点

输出描述

按照横坐标大小，从小到大输出每个点的横纵坐标，每个点占一行。

示例1

输入

3
1 1
2 2
3 3

输出

3 3

一个简单的结构体排序，过得居然还没D多，我震惊了，感觉思想很简单，所有点按横坐标排好序后从右往左遍历一遍即可：

#includeusing namespace std;
typedef long long ll;struct node {int x, y;
} p[500005];bool cmp(node a, node b) {if (a.x != b.x) return a.x < b.x;else if (a.y != b.y) return a.y < b.y;
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) {scanf("%d%d", &p[i].x, &p[i].y);}sort(p, p + n, cmp);int line = 0;vector<node> q;for (int i = n - 1; i >= 0; i--) {if (i == n - 1) {line = p[i].y;q.push_back(p[i]);}else if (p[i].y > line) {line = p[i].y;q.push_back(p[i]);}else continue;}sort(q.begin(), q.end(), cmp);for (int i = 0; i < q.size(); i++) {printf("%d %d\n", q[i].x, q[i].y);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！