Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:发一个最强的注释版的代码,保管一看就懂。

Posted by 3272621977 at 2021-11-05 22:40:17 on Problem 3579
In Reply To:发一个最强的注释版的代码,保管一看就懂。 Posted by:zoujing1978 at 2017-07-26 00:27:50
> /*
> 题意:给定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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator