题解 | #ZJ13 最大点集#(排序)

解题思路

1.数组所有点横坐标不一样,按横坐标升序排列,最大点其实就是横坐标或纵坐标大于等于其他所有点的点;当前i位置点能成为最大点的条件是,i的纵坐标大于等于[i+1:n-1]区间位置点的纵坐标,故逆序遍历数组,x保存[i+1:n-1]区间最大纵坐标值,当i的纵坐标大于等于x时,当前点即为最大点,保存当前点的坐标,最后逆序输出坐标值;

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n ;
    cin >> n;
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), [&](pair<int, int>& p1, pair<int, int>& p2){
        return p1.first < p2.first; //所有点横坐标不一样,按横坐标升序排列
    });
    vector<pair<int, int>> ans;
    for(int i = n - 1, x = 0; i >= 0; i--){ //逆序遍历,如果当前元素的纵坐标大于等于x,则当前元素即为最大点
        if(v[i].second >= x){
            ans.push_back({v[i].first, v[i].second});
            x = v[i].second; //x为纵坐标的最大值
        }
    }
    int m = ans.size();
    for(int i = m - 1; i >= 0; i--){ //需要逆序输出
        cout << ans[i].first << " " << ans[i].second << endl;
    }
    return 0;
}