一本通-1230：寻找平面上的极大点（单调栈，贪心）

【题目描述】 在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x≥a,y≥b;

用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。

给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。

编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。

本题规定：n不超过100，并且不考虑点的坐标为负数的情况。

【输入】 输入包括两行，第一行是正整数n，表示是点数，第二行包含n个点的坐标，坐标值都是整数，坐标范围从0到100，输入数据中不存在坐标相同的点。

【输出】 按x轴坐标最小到大的顺序输出所有极大点。

输出格式为:(x1,y1),(x2,y2),...(xk,yk)(x1,y1),(x2,y2),...(xk,yk)。

注意：输出的每个点之间有","分隔,最后一个点之后没有",",少输出和多输出都会被判错。

【输入样例】 5 1 2 2 2 3 1 2 3 1 4

【输出样例】 (1,4),(2,3),(3,1)

【提示】

---

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int x, y;
    bool operator<(const Node & obj) const
    {
        return ((x < obj.x) || (x == obj.x && y < obj.y));
    }
};

int n;
vector<Node> seq(105);

void solve()
{
    sort(seq.begin(), seq.begin() + n);

    stack<Node> s;
    Node tmp = seq[0];
    for (int i = 0; i < n; ++i) {
        if (seq[i].y < tmp.y) {
            while (!s.empty() && tmp.y >= s.top().y) s.pop();
            s.push(tmp);
        }
        tmp = seq[i];
    }
    while (!s.empty() && tmp.y >= s.top().y) s.pop();
    s.push(tmp);

    stack<Node> help;
    while (!s.empty()) {
        help.push(s.top()); s.pop();
    }

    while (!help.empty()) {
        cout << "(" << help.top().x << "," << help.top().y << ")";
        help.pop();
        if (!help.empty()) cout << ",";
    }
    cout << endl;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i].x >> seq[i].y;
    }

    solve();

    return 0;
}

解析：横纵坐标同时考虑较为困难，可以先按照左端点排序，左端点相同则右端点升序。这样后续的点的横坐标就一定大于前面所有点的横坐标，那么只需要考虑纵坐标是否可能包含前面的极大点。比如序对

1,2 1,4 2,2 2,3 3,1
极大点为1,4 2,3 3,1

会发现，每个极大点对都出现在纵坐标出现逆序的时候，也就是从1，4到2，2的时候，2，3到3，1的时候。那么就可以用一个栈来维护前面选出来的点。当出现逆序的时候触发推入条件，推入的时候，如果被推入的点的纵坐标大于栈内的点的纵坐标，意味着可以被覆盖，那么栈顶的点对就被弹出，直到栈顶的纵坐标大于被推入的点的纵坐标。也就是栈维护纵坐标降序。左后把栈内的元素输出即可。