【JZOJ3854】【NOIP2014八校联考第2场第2试9.28】分组(group)
2024-08-26 01:52:02
MEi
Bsny所在的精灵社区有n个居民,每个居民有一定的地位和年龄,ri表示第i个人的地位,ai表示第i个人的年龄。
最近社区里要举行活动,要求几个人分成一个小组,小组中必须要有一个队长,要成为队长有这样的条件:
1、队长在小组中的地位应该是最高的(可以并列第一);
2、小组中其他成员的年龄和队长的年龄差距不能超过K。
有些人想和自己亲密的人组在同一个小组,同时希望所在的小组人越多越好。比如x和y想在同一个小组,同时希望它们所在的小组人越多越好,当然,它们也必须选一个符合上述要求的队长,那么问你,要同时包含x和y的小组,最多可以组多少人?
LUA
如果选定一个人做队长,那么可以组队的人是一定的。
所以我们容易预处理出每个人做队长的队伍人数:
给所有人按地位从小到大枚举,每枚举一个人便把他的年龄加入一棵权值线段树,然后也容易从权值线段树中得出地位比他低并且年龄与它差距K的人数。
我们考虑对于一个询问而言,所选的队长必须满足:
1.地位大于或等于这两个人的地位最大值;
2.与两个人的年龄差不超过K。
在上述基础上,选择一个组队人数最多的队长。
首先满足第一个条件·,就离线把询问的所需地位从大到小排序,
然后每枚举一个询问,就把所有地位大于这个询问所需地位的人加进另一棵权值线段树。
然后这个询问的答案也容易从这棵权值线段树中得到,也即在满足第二个条件的区间中查找组队人数最多的队长。
最新文章
- Python 过算符和数据类型
- linux常用命令-文件处理命令
- EF 未应用自动迁移,因为自动迁移会导致数据丢失的解决办法
- 推荐15款最好的 Twitter Bootstrap 开发工具
- 使用TFS+GIT实现分布式项目管理
- 【读书笔记】iOS-UIWindow-WindowLevel
- nginx反向代理原理和配置讲解
- Asp.Net-创建网站的快捷方式到桌面,开始菜单,收藏夹
- 【bzoj1212】 [HNOI2004]L语言
- linux学习(一个) 在unbuntu通过添加新的用户
- 聚类系数(clustering coefficient)计算
- 201521123027 《JAVA程序设计》第四周学习总结
- SpringMVC HelloWorld实例开发及部署
- Smart-image通过SoftReference提高性能
- nodejs简单数据迁移demo
- 笔记:Maven 生命周期与命令行详解
- day22 模块最后的补充。包。
- Linux学习笔记之十一————Linux常用服务器构建之ssh和scp
- CUDA 7.0 速查手册
- Ts中的接口interface(属性也能继承...)
热门文章
- 【MFC】MFC文本框中显示浮点数
- 【DM642学习笔记三】flash的烧写
- 如何让 J2Cache 在多种编程语言环境中使用
- 2018-2-13-win10-uwp-设置启动窗口大小--获取窗口大小
- python 与 selenium 学习笔记
- leetcode 321 Create Max Number
- [Array]167. Two Sum II - Input array is sorted
- ubuntn右上角小键盘消失及fictx切换输入法快捷键
- [Array]189. Rotate Array
- TZ_06_SpringMVC_异常处理,自定义异常