首页 > 其他 > 详细

牛客网NOIP赛前集训营-提高组(第一场)

时间:2018-09-10 20:51:57      阅读:314      评论:0      收藏:0      [点我收藏+]

牛客的这场比赛感觉真心不错!!

打得还是很过瘾的。水平也比较适合。

T1:中位数:

题目描述

小N得到了一个非常神奇的序列A。这个序列长度为N,下标从1开始。A的一个子区间对应一个序列,可以由数对[l,r]表示,代表A[l], A[l + 1], ..., A[r]这段数。对于一个序列B[1], B[2], ..., B[k],定义B的中位数如下:
1. 先对B排序。得到新的序列C。
2. 假如k是奇数,那么中位数为技术分享图片。假如k为偶数,中位数为技术分享图片
对于A的所有的子区间,小N可以知道它们对应的中位数。现在小N想知道,所有长度>=Len的子区间中,中位数最大可以是多少。
 
题解
这个题一看就很套路了。
二分一个mid,然后赋值-1/1
 
关于区间中位数什么的题目,做了几道以后,可以考虑向二分答案,然后0/1或者-1/1 赋值判断。
当然还要注意,偶数长度中位数是取哪一个。
类似的题目:
中位数、国际集训队middle;(这两道是中位数)
还有一个 [HEOI2016/TJOI2016]排序 (这个题也是二分然后0/1排序)
本质上都是利用绝对大小没有用,利用相对大小的关系,牺牲一个logn的复杂度,将序列变成0/1或者-1/1的序列,可以大大简化难度,也比较容易判断。
注意边界情况等。
 
 

牛客网NOIP赛前集训营-提高组(第一场)

原文:https://www.cnblogs.com/Miracevin/p/9622678.html

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