Newcoder 小白月赛20 H 好点

自我感觉不错然后就拿出来了.

读读题之后我们会发现这是让我们求一堆数，然后这些数一定是递减的.
就像这样我们选的就是框起来的，然后我们可以看出来这一定是一个单调递减的.
求解的时候可以将按照横坐标从大到小排序.然后如果横坐标相等那么按照纵坐标从大到小排序.
因为我们要求的是他的右上角上没有点。
那么我们就可以直接从上边到下边找了，然后我们可以用一个s来记录到目前为止最大的纵坐标.
如果下一个坐标的纵坐标比上一个的大，那么就说明这是单减的.

别忘了最后的时候把得到的坐标按照横坐标排序啊,
反正我想出来之后5min就做完了....

自己yy一下就好.

code

#include <bits/stdc++.h>

#define N 500010
#define M 1010

using namespace std;
int n, a, b, sum;
struct node {
    int a, b;
}point[N], ans[N];

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

bool cmp(node a, node b) {
    return a.a == b.a ? a.b > b.b : a.a > b.a;
}

bool cmp2(node a, node b) {
    return a.a < b.a;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++)
        point[i].a = read(), point[i].b = read();
    sort(point + 1, point + n + 1, cmp);
    int mii = point[1].b;
    ans[1].a = point[1].a, ans[1].b = point[1].b, sum = 1;
    for (int i = 2; i <= n; i++) {
        if (mii < point[i].b) {
            mii = point[i].b;
            ans[++sum].a = point[i].a;
            ans[sum].b = point[i].b;
        }
    }
    sort(ans + 1, ans + sum + 1, cmp2);
    for (int i = 1; i <= sum; i++)
        cout << ans[i].a << " " << ans[i].b << "\n";
    return 0;
}