POJ3579 Median 寻找第K大数

? ? ? ? 题目大意：N个数，两两之间的差的绝对值有m（C(n,2)）个，计算出这些绝对值中中位数是多少。N范围是 不超过10万。

? ? ? ? 这题其实就是查找第K大数。但是由于N最多会有10W，所以将它们的差的绝对值全部求出来然后排个序的话会很耗时，也很占用内存。这里我们可以用二分法搜索它们的中位数。设C(x)：=差的绝对值不小于X的个数不小于K（这题中K就是中位数-1）。关于如何判断C是否成立，首先对N个数进行排序，这时每一个数与它之前的每个数的差是递增的，这里我们也可以用二分法计算出差的绝对值不小于X的个数。

#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>

using namespace std;

int values[100001];

int compp(const void* a1,const void* a2)
{
	return *(int*)a1 - *(int*)a2;
}

//不小于X的个数不少于K
bool CC(int x,int n,int k)
{
	int curcount = 0;
	
	int l = -1;
	for (int i = 1; i < n;i++)
	{
		
		int r = i;
		while (r - l > 1)
		{
			int mid = (r + l) / 2;
			if (values[i] - values[mid] >= x)
			{
				l = mid;
			}
			else
				r = mid;
		}

		curcount += (l + 1);
		
		
		if (curcount >= k)
		{
			return true;
		}
	}
	if (curcount < k)
	{
		return false;
	}
	else
		return true;
}

int main()
{
#ifdef _DEBUG
	freopen("e:in.txt","r",stdin);
#endif
	int n;
	while (scanf("%d",&n) != EOF)
	{
		int maxvalue = 0;
		for (int i = 0; i < n; i++)
		{
			scanf("%d",&values[i]);
			if (values[i] > maxvalue)
			{
				maxvalue = values[i];
			}
		}
		qsort(values,n,sizeof(int),compp);
		int l = 0;
		int r = maxvalue + 1;
		int m = n * (n - 1) / 2;
		int k = m - (m + 1) / 2 + 1;
		while (r - l > 1)
		{
			int mid = (r + l) / 2;
			if (CC(mid,k))
			{
				l = mid;
			}
			else
				r = mid;
		}
		printf("%dn",l);
	}
	return 1;
}