[POJ 3579] Median【二分答案】

  • 2017-12-29
  • 0
  • 0

Problem:

Time Limit: 1000MS Memory Limit: 65536K

Description

Given N numbers, X1X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i  j  N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th  smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of = 6.

Input

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1X2, ... , XN, ( X≤ 1,000,000,000  3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample Input

4
1 3 2 4
3
1 10 2

Sample Output

1
8

Source

POJ Founder Monthly Contest – 2008.04.13, Lei Tao

Solution:

首先将 X[] 排序,然后在区间[0, X[n] - X[1]]上二分差值即可。

check 时利用 X[] 的单调性,使用哨兵 i, j 维护小于等于当前差值的区间,复杂度为 O(n)。

Code: O(Tnlogn) [296K, 329MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N, X[100005], medianId;

inline bool check(const int &val){
	int cnt = 0;
	for(register int i = 1, j = 1; i <= N; i++){
		while(j < N && X[j + 1] - X[i] <= val) j++;
		// Maintain the region where differences are smaller than val
		cnt += j - i;
	}
	return cnt >= medianId;
}

int main(){
	while(scanf("%d", &N) != EOF){  // Read this way without terminator
		medianId = (N * (N - 1) >> 1) + 1 >> 1;  // Beware of the order of median
		for(register int i = 1; i <= N; i++) scanf("%d", X + i);
		sort(X + 1, X + N + 1);
		int lft = 0, rt = X[N] - X[1];
		while(lft < rt){
			int mid = lft + rt >> 1;
			if(check(mid)) rt = mid;
			else lft = mid + 1;
		}
		printf("%d\n", lft);
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai