POJ-3579-Median

题目描述：

Given N numbers, X1, X2, … , 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 m = 6.

输入：

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 X1, X2, … , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

输出：

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

输入示例：

1
2
3
4
4
1 3 2 4
3
1 10 2

输出示例：

1
2
1
8

题目大意：

给定N个数，求每两个数的差的绝对值一共C(N,2)个，排序后的中位数。

思路：

首先对于差的绝对值，我们只需要预先对数组进行排序，作后面对前面的差就不会出现负数。

我们考虑二分来解决该问题。答案是排序后的中位数，具有单调性，所以可以使用二分。我们先找到一个目标值，用这个目标值去判断是否为要求的中位数。

如何判断该数是否满足条件呢？
如果枚举全部这C(N,2)个数需要O(N2)的复杂度，超出了题目的要求，所以要寻找新的方案。我们已经将原数组排好序了，以每一项开始到数组最后，我们二分的寻找这里的所有的关系（i与i+1,i+2,…,N-1）中，满足：

1
arr[j] - arr[i] <= x

的一共有几项。

统计出项数与中位数作比较，就可以判断目标值是否满足条件。

Solution：

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
/*
 * @Date: 2019-10-05 13:59:05
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-05 14:48:00
 */
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 1e5+10;

int N;
int arr[MAXN];

bool check(int x){
    int cnt = 0;
    int M = N*(N-1)/2;
    M = (M+1)/2;
    for(int i = 0; i < N; i++){
        int l = i, r = N-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(arr[mid] - arr[i] <= x) l = mid;
            else r = mid-1;
        }
        cnt += l-i;
        // arr[mid] - arr[i] <= x -----> arr[mid] <= arr[i]+x
        // 所以找arr[i]+x 的 upper_bound。
        // (upper_bound(arr,arr+N,arr[i]+x)-arr)-1 长度
        // (upper_bound(arr,arr+N,arr[i]+x)-arr)-i-1 //减去偏移量
        // cnt += (upper_bound(arr,arr+N,arr[i]+x)-arr)-i-1;
    }
    return cnt >= M;
}

int main(){
    freopen("in.txt","r",stdin); 
    while(scanf("%d",&N)!=EOF && N){
        for(int i = 0; i < N; i++){
            scanf("%d",&arr[i]);
        }
        sort(arr,arr+N);
        int l = 0, r = arr[N-1];
        //对结果进行二分
        while(l < r){
            int mid = l+r>>1;
            // 检查该结果是否大于等于总数的一半，
            if(check(mid)) r = mid;
            else l = mid+1;
        }
        printf("%d\\n",l);
    }
    return 0;
}