本文共 2190 字，大约阅读时间需要 7 分钟。
在矩阵上，我们可以通过三种基本操作来处理点标记问题：标记、去除标记以及查找比某点坐标更大的最小点。这个问题可以通过C++中的set集合容器来高效解决。
set集合在C++中被广泛应用于需要自定义排序和快速查找操作的场景。在这个问题中，点的坐标可以看作是可比较的对象，因此可以通过定义适当的比较运算符将结构体或pair类型存储在set中。
set集合的基础使用
set集合是一个自动排序的数据结构，支持快速查找和插入操作。要使用set，我们需要定义一个能比较两个对象大小的运算符。如果使用结构体节点（struct），需要重载比较运算符。例如：struct node { int x, y;};bool operator<(const node& a, const node& b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x;}set st; 但是，直接定义set
元素增删操作
set集合支持以下操作：set.erase(it)：通过迭代器移除集合中的特定元素。set.erase(e)：通过元素对象直接移除集合中的对应元素。set.lower_bound(val)：找到第一个大于等于val的元素位置。set.upper_bound(val)：找到最后一个小于等于val的元素位置。查找操作
在本题中，我们需要查找比点(x, y)坐标更大的最小点。可以通过set的lower_bound方法找到第一个大于等于目标点的位置，然后从该位置开始向后遍历，找到第一个满足条件的点。由于查找操作需要在有序集合中高效完成，set集合的优势在于其自动排序功能和快速查找能力。通过将点存储在set中，我们可以在O(log n)时间内完成插入、删除和查找操作。
具体步骤如下：
#include#include #include #include using namespace std;struct node { int x, y;};bool operator<(const node& a, const node& b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x;}int main() { char s[8]; int n, cas, ans; set st; set ::iterator it; cas = 1; while (scanf("%d", &n) != EOF) { st.clear(); printf("Case %d:\n", cas++); for (; n--; ) { scanf(" %s %d %d", s, &st.insert(node).x, &st.insert(node).y); if (strcmp(s, "add") == 0) { // 添加标记点 } else if (strcmp(s, "remove") == 0) { // 删除标记点 node nd; scanf(" %s %d %d", s, &nd.x, &nd.y); st.erase(nd); } else { // 查找比当前点坐标更大的最小点 node target; scanf(" %s %d %d", s, &target.x, &target.y); auto it = st.lower_bound(target); bool found = false; for (; it != st.end(); ++it) { if (it->x > target.x && it->y > target.y) { printf("%d %d\n", it->x, it->y); found = true; break; } } if (!found) { printf("-1\n"); } } printf("\n"); } } return 0;}
这种实现方法充分利用了set集合的优势，确保了在处理大规模矩阵时的高效性和正确性。
转载地址：http://mudwz.baihongyu.com/