题意:训练之南P228
分析:照着书上的做法,把点插入后把它后面不占优势的点删除,S.size ()就是优势的人数,时间复杂度O (nlogn)
#include <bits/stdc++.h> using namespace std; struct Point { int a, b; Point() {} Point(int a, int b) : a (a), b (b) {} bool operator < (const Point &r) const { return (a < r.a || (a == r.a && b < r.b)); } }; multiset<Point> S; multiset<Point>::iterator it; int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { S.clear (); printf ("Case #%d:\n", ++cas); int n; scanf ("%d", &n); for (int x, y, i=1; i<=n; ++i) { scanf ("%d%d", &x, &y); Point p (x, y); it = S.lower_bound (p); if (it == S.begin () || (--it) -> b > y) { S.insert (p); it = S.upper_bound (p); while (it != S.end () && it -> b >= y) S.erase (it++); } printf ("%d\n", S.size ()); } if (T) puts (""); } return 0; }
STL(multiset) UVA 11020 Efficient Solutions
原文:http://www.cnblogs.com/Running-Time/p/5123793.html