UESTC_基爷的中位数 2015 UESTC Training for Search Algorithm & String

时间：2021-09-24 11:00:28

D - 基爷的中位数

Time Limit: 5000/3000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

给你N个数，X1,X2,...,XN, 基爷让我们计算任意两个数差的绝对值 ∣Xi−Xj∣ (1≤i<j≤N) 。 这样，我们可以得到 C2N 个数。

现在，基爷希望聪明的你能用一个简单的程序求出这 C2N 个数的中位数！

Input

输入有多组数据。

每组数据，第一行一个整数 N，第二行给出 N 个整数 X1,X2,...,XN （ |Xi|≤1,000,000,000; 3≤N≤100,000 ）

Output

按要求输出中位数，每个数占一行。

Sample input and output

Sample Input Sample Output 
4

1 3 2 4

3

1 10 2
 
1

8

Hint

当这 C2N 个数的个数为偶数 M 的时候，取第 ⌊M2⌋ 个最小的数作为中位数 （ 别问为什么，这就是基爷的中位数！ ）

解题报告:

排序之后二分答案，每次找位置也是二分，总复杂度 olognlogx,每次找严格小于这个数的数有多少个!!

总之。。注意细节（我挂了35发)

#include <iostream>

#include <algorithm>

typedef long long ll;

using namespace std;

const int maxn = 1e5 + ;

ll x[maxn];

ll n;

int main(int argc,char *argv[])

{

  while(~scanf("%lld",&n))

   {

         for(int i =  ; i < n ; ++ i) scanf("%lld",&x[i]);

         sort(x,x+n);

         ll r = 5e9 ,  l= -5e9;

         ll tar = n*(n-)/;

         if (tar & )

          tar /= ;

         else

          tar = tar /  - ;

         //小于等于目标位置的有多少个数

         while(r > l)

          {

                ll mid = l + (r-l + ) / ;

             ll rank = ;

             for(int i =  ; i < n -  ; ++ i)

              rank += (lower_bound(x+i+,x+n,mid+x[i])-(x+i+)); // 小于该数的有几个

             if (rank > tar)

              r = mid - ;

             else

              l = mid;

       }

      printf("%lld\n",r);

   }

  return ;

}

相关文章