> /*
> 题意：给定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:发一个最强的注释版的代码，保管一看就懂。 (3) 3272621977 2021-11-05 22:40:36