# [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:

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
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

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