博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 11020 - Efficient Solutions(set)
阅读量:6405 次
发布时间:2019-06-23

本文共 953 字,大约阅读时间需要 3 分钟。

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;}

转载地址:http://bejea.baihongyu.com/

你可能感兴趣的文章
[转]如何将WCF服务发布到IIS中去VS2010版
查看>>
TestNG之注解的生命周期
查看>>
iOS工程引入ios-charts-master
查看>>
12C 对表分区维护的增强
查看>>
前序-中序-后序-非递归-实现
查看>>
Map 3D中程序设置地图中心点
查看>>
一个非常超级可爱的滚动到顶端(Back to top)的jQuery插件- jQuery Back to Top
查看>>
Datafix_for_arinvoice_dist_move
查看>>
让人期待的2011年度最佳 jQuery 插件发布啦
查看>>
UVA 10154 Weights and Measures
查看>>
俞敏洪在清华励志演讲
查看>>
网络七层协议的形象说明
查看>>
base与this
查看>>
【转载】C# ??(问问,问号问号)运算符,可空值(申明加?(问号))的克星
查看>>
jQuery.protoype.xxx=function(){}
查看>>
SGU 109 Magic of David Copperfield II
查看>>
认清SQL_Server_2005的基于行版本控制的两种隔离级别
查看>>
c#在WinForm中重写ProgressBar控件(带%的显示)
查看>>
开源爬虫larbin分析
查看>>
C# Linq获取两个List或数组的差集交集
查看>>