首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。