UVA 11020 - Efficient Solutions(set)

本文主要是介绍UVA 11020 - Efficient Solutions(set)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 11020 - Efficient Solutions

题目链接

题意：每个人有两个属性值(x, y)，对于每一个人(x,y)而言，当有另一个人(x', y'),如果他们的属性值满足x' < x, y' <= y或x' <= x, y' < y的话，这个人会失去优势，每次添加一个人，并输出当前优势人个数

思路：由于每个人失去优势后，不可能再得到优势，所以失去优势就可以当成删去这些点，这样的话，就可以用一个multiset来维护点集，每次加入一个点，利用lowerbound，upper_bound二分查找旁边点的位置来进行判断和删点

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;int t, n;
struct Point {int x, y;bool operator < (const Point &c) const {if (x == c.x) return y < c.y;return x < c.x;}
};multiset<Point> s;
multiset<Point>::iterator it;int main() {int cas = 0;cin >> t;while (t--) {s.clear();cin >> n;Point u;cout << "Case #" << ++cas << ":" << endl;while (n--) {cin >> u.x >> u.y;it = s.lower_bound(u);if (it == s.begin() || (--it)->y > u.y) {s.insert(u);it = s.upper_bound(u);while (it != s.end() && it->y >= u.y) s.erase(it++);}cout << s.size() << endl;}if (t) cout << endl;}return 0;
}

这篇关于UVA 11020 - Efficient Solutions(set)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---