UVA 11020 Efficient Solutions+multiset的应用

分类：数据结构

UVAmultiset

题目链接：点击进入首先来讲，很容易看到我们其实只要维护优势人群的集合；如果加入一个新的人，我们首先看一下优势人群中是否有人会让这个人失去优势，如果没有，则将这个人插入集合中，但要注意到这个人的插入可能会让其它的人失去优势。所以要求这个集合要能支持快速查询和修改操作；而multiset恰好能能满足这个需要。代码如下：

;struct Point{int a,b;<(const Point& rhs) const{return a<rhs.a||(a==rhs.a&&b<rhs.b);}};multiset<Point>S;multiset<Point>::iterator it;int main(){//freopen(“in.txt”,”r”,stdin);int T;scanf(“%d”,&T);for(int Case=1;Case<=T;Case++){if(Case!=1)printf(“\n”);printf(“Case #%d:\n”,Case);int n,a,b;scanf(“%d”,&n);S.clear();while(n–){scanf(“%d%d”,&a,&b);Point P=(Point){a,b};it = S.lower_bound(P); ///在红黑树中查找第一个小于P的元素if(it==S.begin()|| (–it)->b >=b ) ///如果P也具有优势{S.insert(P);it = S.upper_bound(P); ///it以后的元素都会被影响while(it!=S.end()&&it->b >=b) S.erase(it++); ///删除掉失去优势的人}printf(“%d\n”,S.size());}} return 0;}

上一篇UVALive 3882–And Then There Was One+约瑟夫环问题变形

顶1踩0

，我想一个人旅行，可以不带相机，也不要带上手机，

相关文章：

你感兴趣的文章：

标签云：