POJ 3579 Median

Median

Time Limit: 1000MS Memory Limit: 65536K

Description

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 Input

4
1 3 2 4
3
1 10 2

Sample Output

1
8

思路：

刚看题目，肯定暴力是最简单的方法，但是数据实在太大了，所以就要用其他方法了，所以就用双重二分了，首先要求出有多少个数，再求中位数的位置就有n * (n - 1) / 4就是中位数的位置了，然后就是如何求出位置了，先找中位数为多少，然后就是找大于等于这个中位数加上i位置的数字的位置，既然能够大于等于那么在这个数字后面的也一定能够大于等于，所以就是用n-位置，0-n-1的数量总和就是大于等于中位数的数量总和，然后用二分的方法确定最后的中位数。

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int a[100010];
int check(int x) {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += n - (lower_bound(a, a + n, a[i] + x) - a);
	}
	return sum;
}
int main() {
	while (scanf("%d", &n) != EOF) {
		m = n * (n - 1) / 4;
		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 (r - l > 1) {
			int mid = (l + r) >> 1;
			if (check(mid) <= m) r = mid;
			else l = mid;
			
		}
		cout << (l + r) / 2 << endl; 
	}
	return 0;
}