/*
题意：给定N个数，两两做差取绝对值，再找出这些绝对值的中位数。也就是给n个数放在数组a中，求出C(n,2)个|a[i] - a[j]|数中的的中位数。
思路：对数组a排序后，估计一个两两做差的绝对值的集合的中位数mid，与a[i]的差大于mid（也就是某个数大于a[i] + mid）的那些数的个数如果小于C(n,2) / 2的话，说明mid太大了。以此为条件进行第一重二分搜索，第二重二分搜索是对X的搜索，直接用lower_bound实现。
*/

#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
#include <cstdio>
using namespace std;

// 计算组合数
long long C(int m, int n)
{
	int p = 1;
	int q = 1;
	for (int i = 1; i <= n; i++)
	{
		p *= (m - i + 1);
		q *= i;
	}
	return p / q;
}

// 判断mid作为中位数是否太大。执行此操作前数组a必须排序。
bool Check(int* a, int n, int mid)
{
	int sum = 0; // 与a[i]的差大于mid（也就是某个数大于a[i] + mid）的那些数的个数之和
	// 遍历每一个a[i]，求大于或者等于mid+a[i]的个数
	for (int i = 0; i < n; i++)
	{
		// lower_bound(a + i + 1, a + n, mid + a[i])表示在a[i+1]到a[n-1]中二分查找大于或者等于mid+a[i]的第一个元素的位置
		sum += (a + n) - lower_bound(a + i + 1, a + n, mid + a[i]); 
	}
	// 如果满足sum <= C(n, 2) / 2，说明大于或等于中位数的元素没有超过半数或者正好等于半数，分为这么4种可能：
	//1、大于或等于中位数mid（我们估计的）的这部分元素包含了这个中位数mid（我们估计的），个数正好等于半数，说明元素个数有偶数个，而后半截的第一个元素是这个中位数mid（我们估计的），显然应该是mid的前一个元素才是真正的中位数，说明mid估大了；
	//2、大于或等于中位数mid（我们估计的）的这部分元素不包含这个中位数mid（我们估计的），个数正好等于半数，说明元素个数有偶数个，而后半截的第一个元素大于mid，前半截最后一个元素小于mid，显然应该是mid的前一个元素才是真正的中位数，说明mid估大了；
	//3、大于或等于中位数mid（我们估计的）的这部分元素包含了这个中位数mid（我们估计的），个数小于半数，说明后半截的第一个元素是这个中位数mid（我们估计的），又因为后半截的元素个数不足半数，显然说明mid估大了；
	//4、大于或等于中位数mid（我们估计的）的这部分元素不包含了这个中位数mid（我们估计的），个数小于半数，说明后半截的第一个元素大于mid（我们估计的），前半截的最后一个元素小于mid，又因为后半截的元素个数不足半数，显然说明mid估大了；
	// 综合1、2、3、4，如果满足sum <= C(n, 2) / 2这种情况反正就是估大了
	return sum <= C(n, 2) / 2; // 返回true就是估大了，返回false就是估小了或者正好
}

int main()
{
	int n = 0;
	//while (cin >> n)
	while(scanf("%d", &n)==1)
	{
		int* a = new int[n];
		for (int i = 0; i < n; i++)
		{
			//cin >> a[i];
			scanf("%d", &a[i]);
		}
		sort(a, a + n);
		long long lb = 0; // 两两做差取绝对值可能的最小值
		long long ub = a[n - 1] - a[0]; // 两两做差取绝对值可能的最大值
		// 为什么循环条件是ub - lb > 1？是因为ub、lb、mid都是整数，由于mid会向下取整，所以当ub-lb=1时，mid为lb，而此时真正的中位数要么为ub，要么为lb，也就是中位数mid要么估的正好，要么估低了，在循环体内，只会走else分支，下届lb被修正为mid，是同样的值，并没有改变，于是陷入死循环，因此循环条件不能写成ub - lb >= 1或者ub - lb >=0，只能写成ub - lb > 1。
		// 当循环条件为ub - lb > 1时，在循环快结束时，必定有ub-lb=2，最终mid的值lb+1，而此时真正的中位数要么为ub，要么为lb，要么为lb+1。
		// 如果真正的中位数为ub，说明mid估低了，在循环体内，走else分支，修正lb的值，在原先的值的基础上加1，得到了真实的中位数的值，随后循环结束；
		// 如果真正的中位数为lb，说明mid估高了，在循环体内，走if分支，修正ub的值，然后循环结束；
		// 如果真正的中位数为lb+1，说明mid估的正好，在循环体内，走else分支，修正lb的值，在原先的值的基础上加1，得到了真实的中位数的值，随后循环结束；
		// 综上，循环条件必须写成ub - lb > 1，循环结束后，lb就是确切的中位数的值
		while (ub - lb > 1)
		{
			int mid = (lb + ub) >> 1; // 尝试新的中位数，
			bool flag = Check(a, n, mid);
			// 如果中位数猜测的太大
			if (flag) 
			{
				ub = mid; // 修改上界。
			}
			// 如果中位数猜测的太小，或者小于中位数的元素个数正好等于半数
			else 
			{
				lb = mid; // 修改下界。
			}
		}
		//cout << lb << "\n";
		printf("%d\n", lb);
		delete[] a;
	}
	return 0;
}

• Re:发一个最强的注释版的代码，保管一看就懂。 (2945) 3272621977 2021-11-05 22:40:17
  • Re:发一个最强的注释版的代码，保管一看就懂。 (3) 3272621977 2021-11-05 22:40:36