首页 > 其他 > 详细

STL(multiset) UVA 11020 Efficient Solutions

时间:2016-01-12 13:37:04      阅读:142      评论:0      收藏:0      [点我收藏+]

 

题目传送门

题意:训练之南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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!