poj 3579 Median (尺取法+二分)

题意:给出n个数,两两做差的绝对值,共有m=n*(n-1)/2个,问其中的中位数是多少。特别地,当m为偶数的时候,中位数为第m/2个。

思路:二分中位数。

一开始还觉得由于中位数在整数意义上不连续不能二分。。。。

但是最后结果不可能是那样的答案啊。。。

check的条件是,以k为中位数的时候,绝对值小于k的数要小于(m+1)/2个(也就是中位数所在的位置)

check的时候尺取即可。

复杂度 排序O(nlgn) + 二分(lgn)*尺取O(n) ,整体O(nlgn)

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz