L - Median

Given N numbers, X1, X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th  smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

Input

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, ... , XN, ( Xi ≤ 1,000,000,000  3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample

4
1 3 2 4
3
1 10 2

1
8

题意：每一组数据给一个n，后面给n个数，求这些数之间的差绝对值的中位数，比如例子1 3 2 4 ，差为1，1，1，2，2，3，如果个数为偶数则取中间前面，奇数取中间的数。

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>
 
using namespace std;
const int N = 1e6 + 10;
vector<int> vv;
 
int n, cha;
//n是输入数的个数，cha是这些数的差的个数
//如4：1 3 2 4有1+2+3个，等差公式：cha = (0+n-1)*n/2;
 
int find(int x)
{
	int sum = 0;
	// 使用二分查找在有序向量v中找到第一个大于等于v[i]+x的位置
	// 然后用向量末尾迭代器减去该位置迭代器，得到大于等于v[i]+x的元素个数
	for (int i = 0; i < n; i++) sum += vv.end()-lower_bound(vv.begin(), vv.end(), vv[i] + x);
	//为什么sum>cha，如果当前mid的差值都大于cha了，那还有l到mid之间的数没有考虑
	//如x = 2,cha = 3,sum = 4，说明在差的序列中有4个2，而且差值为0到2还没考虑，显然2就不是我们要找的数了，应该在0到2中去找
	if (sum > cha) return 1;  //注：不能等于，道理同上
	else return 0;
}
int main()
{
	while (cin >> n)
	{
		vv.clear();
		for (int i = 0; i < n; i++)
		{
			int num; scanf_s("%d", &num);
			vv.push_back(num);
		}
 
		sort(vv.begin(), vv.end());
 
		cha = (n - 1) * n / 2;
 
		cha /= 2;
 
		int l = 0, r = vv[n - 1] - vv[0] + 1;
 
		//差值的最小为0，最大为数组中最大与最小的数的差加一
		//每次进行二分，如果二分得到的差值(设为x),如果存在与当前的数(设为v[i])的个数(即v[i]+x)大于我们要找的位置，则在mid和r之间，都在在l和mid之间
		//差值越大数越少，差值越小数越多
		while (l < r)
		{
			int mid = (l + r + 1) / 2;
			if (find(mid))l = mid;
			else r = mid-1;
		}
		cout << l << endl;
	}
}