题解 | 匹配星星

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct Star {
    int x, y, z;   // 坐标和属性，z = 0 或 1
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

    // 排序规则：先按 x 升序，若 x 相同则按 z 降序（即 z=1 的右点排在 z=0 的左点前面）
    // 这样保证了当 x 相等时，右点先被处理，不会错误地与相同 x 的左点匹配（因为要求严格小于）
    sort(stars.begin(), stars.end(), [](const Star & a, const Star & b) {
        if (a.x != b.x) return a.x < b.x;
        return a.z > b.z;   // z=1 在前，z=0 在后
    });

    multiset<int>
    leftY;   // 存储所有可用的左点（z=0）的 y 坐标，允许重复
    int ans = 0;

    for (const auto& s : stars) {
        if (s.z == 0) {
            // 左点：将其 y 加入集合，等待与后面的右点匹配
            leftY.insert(s.y);
        } else { // s.z == 1
            // 右点：从集合中找一个 y 比当前 y 小的最大左点 y 进行匹配
            // 使用 lower_bound 找到第一个 >= s.y 的位置，前一个就是 < s.y 的最大值
            auto it = leftY.lower_bound(s.y);
            if (it != leftY.begin()) {
                --it;                 // 指向小于 s.y 的最大 y
                leftY.erase(it);      // 删除这个左点，它被匹配了
                ++ans;
            }
            // 如果找不到，则跳过该右点
        }
    }

    cout << ans << endl;

    return 0;
}