UVA 11020 - Efficient Solutions
题意:每个人有两个属性值(x, y)。对于每个人(x,y)而言,当有还有一个人(x', y'),假设他们的属性值满足x' < x, y' <= y或x' <= x, y' < y的话,这个人会失去优势,每次加入一个人,并输出当前优势人个数
思路:因为每一个人失去优势后,不可能再得到优势,所以失去优势就能够当成删去这些点,这种话。就能够用一个multiset来维护点集。每次增加一个点,利用lowerbound。upper_bound二分查找旁边点的位置来进行推断和删点
代码:
#include#include #include #include 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 s;multiset ::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;}