Descriptions

给N数字, X1, X2, … , XN，我们计算每对数字之间的差值：∣Xi - Xj∣ (1 ≤ i ＜ j ≤N). 我们能得到 C(N,2) 个差值，现在我们想得到这些差值之间的中位数。

如果一共有m个差值且m是偶数，那么我们规定中位数是第(m/2)小的差值。

Input

输入包含多测
每个测试点中，第一行有一个NThen N 表示数字的数量。
接下来一行由N个数字：X1, X2, … , XN
( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

Output

对于每个样例，输出中位数即可。

Sample Input

4
1 3 2 4
3
1 10 2

Sample Output

1
8

题解

二分中位数，如果小于等于mid的|a[i]-a[j]|的个数大于等于m，说明右边界过大，否则左边界过小。

查找小于等于mid的|a[i]-a[j]|的个数时使用upper_bound来查找,找到的是第一个大于a[i]+x的元素的地址。

所以在计算小于等于a[i]+x的个数时,cnt+=(upper_bound(a+i,a+n,a[i]+x)-(a+i))-1;(注意最后要减一)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=1e5+10;
int a[N];
LL n,m;

LL check(int mid)
{
    //检验mid为中位数时<=mid的|a[i]-a[j]|的个数
    LL cnt=0;
    for(int i=0;i<n;i++)
        cnt+=(upper_bound(a+i,a+n,a[i]+mid)-a-i)-1;

    return cnt;
}

int main()
{
    while(~scanf("%lld",&n))
    {
        m=n*(n-1)/2;
        if(m & 1) m=m/2+1;
        else m=m/2;

        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);

        int l=0,r=a[n-1]-a[0];
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(mid) >= m) r=mid;
            else l=mid+1;
        }

        cout<<l<<endl;
    }
    //system("pause");
}