自动搬运

查看原文

来自洛谷，原作者为

	shiningrise **

搬运于2025-08-24 21:41:27，当前版本为作者最后更新于2018-01-06 19:02:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在纸上把测试数据一画，就知道

贪心 先按y排序，y相同按x排序

第一点肯定就是极大点了，因为没有点y比他大

接下来就把这个极大点的x记下，之后第一个出现x比前一个极大点x大的点就是极大点

    #include<bits/stdc++.h>
    using namespace std;
    struct Node {
        int x;int y;
        bool operator <(const Node &b)const
        {
            if(y==b.y)return x>b.x; 
            return y>b.y;
        }
    }a[500005];
    int main()
    {
         std::ios::sync_with_stdio(false);
        int n;
        cin>>n; 
        for(int i=0;i<n;i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        sort(a,a+n);
        int f=1;
        int last =-1;
        for(int i=0;i<n;i++)
        {
            if(a[i].x>last)
            {
                last = a[i].x;
                if(f)f=0;else cout<<",";
                cout<<"("<<a[i].x<<","<<a[i].y<<")";
            }
        }
        return 0;
    }