首页 > 代码库 > uva11020 set
uva11020 set
有n个人，每个人有两个属性x,y。如果对于一个人P(x,y) 不存在另外一个人(x‘,y‘) 使得x‘<x,y‘<=y 或者 x‘<=x,y‘<y 我们说p是有优势的，每次给出一个人的信息，要求输出在只考虑当前已获得信息的前提下，多少人是有优势的。
set 可以用lower_bound 把点插入，然后不断的去修改。
#include <iostream>#include <cstdio>#include <set>using namespace std;struct point{ int x , y ; bool operator < ( point A)const { return x<A.x||(x==A.x&&y<A.y); }};multiset<point> S;multiset<point>::iterator it;int main(){ int T; scanf("%d",&T); for(int kase=1; kase<=T; ++kase){ if(kase>1) printf("\n"); printf("Case #%d:\n",kase); 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); if(it==S.begin()||(--it)->y>p.y){ S.insert(p); it=S.upper_bound(p); while(it!=S.end()&&it->y>=p.y)S.erase(it++); } printf("%d\n",S.size()); } } return 0;}
uva11020 set
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。