【POJ No. 3579】 差的中位数 Median

【POJ No. 3579】 差的中位数 Median

官方题目地址

【题意】

给定N 个数X 1 , X 2 ,…, X N ，计算每一对数字的差：|Xi -Xj |，1≤i ＜j ≤N 。尽快找到差的中位数

这个问题中，中位数被定义为 第 m / 2 个数，m 为差的数量

【输入输出】

输入：

由几个测试用例组成。每个测试用例的第1行都为N 。然后给出N 个数字，表示X 1 , X 2 ,…, X N （ Xi ≤10^9 ，3≤N ≤10^5）。

输出：

对于每个测试，都单行输出差的中位数。

【样例】

【算法设计】

本题数据量较大，N ≤10^5 ，如果枚举每两个数的差，然后找中位数，则时间复杂度为O (N^2 )，N^2 ≤10^10 ，时间限制为1秒，显然超时。

可以采用二分法查找差的中位数。使用algorithm头文件中的lower_bound()函数查找第1个大于或等于a [i]+val的数，统计有多少个数与a [i]的差值大于或等于val。

1. 对序列排序。 (sort() 函数)
2. 二分查找，如果差值大于或等于mid 的数多于一半，则向后查找，否则向前查找。

【算法实现】

#include
#include

using namespace std;

const int maxn = 1e5 + 1000;

int a[maxn] , n , m;

bool check(int val){ //检查有多少个数的差大于或等于val 
	
	int cnt = 0;
	
	for(int i = 0; i < n ; i++){
		
		cnt += n - (lower_bound(a , a + n , a[i] + val) - a);
		
	}
	return cnt > m;
}

int main(){
	
	while(~scanf("%d" , &n)){
		
		m = n * (n - 1) / 4;
		
		int ans = -1;
		
		for(int i = 0 ; i < n ; i++){
			
			scanf("%d" , &a[i]);
			
		}
		
		sort(a , a + n);
		
		int l = 0;
		int r = a[n - 1] - a[0];
		
		//二分查找 
		while(l <= r){
			
			int mid = (l + r) / 2;
			
			if (check(mid)){
				
				ans = mid;
				l = mid + 1;
				
			}
			else{
				r = mid - 1;
			}
			
		}
		printf("%d\n", ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

【完美图解】

以样例1
1、3、2、4，求差的中位数

① 排序

② 二分搜索

m = n * (n - 1) / 4 = 3;
l = 0;
r = a[n - 1] - a[0] = 3;
1
2
3

求解：

1. mid = (l + r) / 2 = 1。统计有多少个数的差大于或等于1
   i =0：第1个大于或等于a [0]+1的下标为1，有n -1=3个数与a [0]的差大于或等于1。
   i =1：第1个大于或等于a [1]+1的下标为2，有n -2=2个数与a [1]的差大于或等于1。
   i =2：第1个大于或等于a [2]+1的下标为3，有n -3=1个数与a [2]的差大于或等于1。
   i =4：第1个大于或等于a [3]+1的下标为n （不存在则为n ），有n -n =0个数与a [3]的差大于或等于1。
   cnt=3+2+1+0=6>m （m =3），差大于或等于1的数多于一半，说明差的中位数在后半部分，ans=mid=1；l =mid+1=2，r =3，继续求解。

2. mid = (l + r) / 2 = 2，统计有多少个数 的差的大于或等于2。
   i =0：第1个大于或等于a [0]+2的下标为2，有n -2=2个数与a [0]的差大于或等于2。
   i =1：第1个大于或等于a [1]+2的下标为3，有n -3=1个数与a [1]的差大于或等于2。
   i =2：第1个大于或等于a [2]+2的下标为n （不存在则为n ），有n -n =0个数与a [2]的差大于或等于2。
   i =4：第1个大于或等于a [3]+2的下标为n （不存在则为n ），有n -n =0个数与a [3]的差大于或等于2。
   cnt=2+1+0+0=3不大于m （m =3），差大于或等于2的数少于等于一半，说明差的中位数在前半部分，r =mid-1=1，此时l =2，不满足二分条件l ≤r ，循环结束。

3. 输出答案 ans = 1。

【算法分析】

排序的时间复杂度为O (n logn )，二分搜索的时间复杂度为O(logX max )，lower_bound()函数内部也是二分查找，时间复杂度为O(logn )，check函数的总时间复杂度为O (n logn )。X max =10^9 ，log10^9 ≈log2^30 ≈30，n ≤10^5 ，n logn ≈10^6 ，在一般情况下，10^7以内均可通过1秒测试。

check函数也可以不调用STL，直接求解：

bool check(int val){
	int cnt = 0 , k = 0;
	for(int i = 0; i < n ; i ++){
		while(k < n && a[k] -a[i] < val){ //找第一个与a[i]的差大于或等于val的数
			k ++;
		}
		cnt += n - k;
	}
	return cnt > m;
}
1
2
3
4
5
6
7
8
9
10

试试速度

现在的check函数充分利用了 a[i] 递增的特性，总时间复杂度为O(n)，速度更快了。

但是排序的时间复杂度是不变的。