poj 3579 Median

Median

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6744		Accepted: 2249

Description

Given N numbers, X₁, X₂, ... , X_N, let us calculate the difference of every pair of numbers: ∣X_i - X_j∣ (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.

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 X₁, X₂, ... , X_N, ( X_i≤ 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
8
Sample Output

题意：给定n个数X1,X2....Xn，对这n个数两两做差，可以得到n*(n-1)/2个差，需要找出差的中位数，即若有k个差，k为偶数，找到第k/2个数，若为奇数，找到第k/2+1个数

思路：需要二重二分法解决，但二分法边界问题难以考虑，提供两种考虑方式，下面那种考虑方式是寻找出所有比'中位数候选人'大的数的个数作为切入点来判断：
第一重二分，目的是为了找到这个中位数的值，第二重二分，是为了判断这个当前值是否处于中位数的位置。那么如何二分判断该值是否处于中位数位置呢：若设当前需要检验的差值diff=Xj-Xi,那么每次固定一个
Xi,找到所有比Xj大的X元素，也就是所有比(diff+Xi)大的X元素，每找到一个元素意味着找到了一个比diff大的差值，当Xi遍历后就能找到所有比diff大的差值，判断比diff大的差值个数是否少于等于k/2个，如果true，
说明也许diff还比较大，可以更小一点（这里特别注意，这样判断是有讲究的，譬如差值是这样的情况：2 5 7 7 9 14，中位数是7，但比7大的差值个数为2，小于3，情况将归于true中），将第一重二分的ub改为mid值，
否则将lb改为mid值，最终中位数的取值范围是(lb,ub],缩小范围后取ub即可。
AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N_MAX = 100000;
typedef unsigned long long ull;
int X[N_MAX],N,m;
bool C(ull mid) {
    ull bigger_num = 0;
    for (int i = 0; i < N;i++) {
        bigger_num += X + N - upper_bound(X+i+1,X+N,X[i]+mid);
    }
     return bigger_num <= m/2;
}
int main() {
    while (scanf("%d",&N)!=EOF) {
        for (int i = 0; i < N; i++) {
            scanf("%d",&X[i]);
        }
        sort(X, X + N);
        ull lb = 0, ub = *max_element(X, X + N) - *min_element(X,X+N)+1;
        m = N*(N - 1) / 2;
        while (ub - lb > 1) {
            ull mid = (ub + lb) / 2;
            if (C(mid))ub = mid;
            else lb = mid;
        }
        printf("%lld
", ub);
    }
    return 0;
}

还有一种考虑方式是寻找出所有比'中位数候选人'小的数的个数作为切入点来判断：
第一重二分还是一样，找到一个'中位数候选人'，接下来的第二重二分来判断这个候选人是否符合中位数的要求，即可以先找出所有比该数小的数的个数，怎么找类似上述方法，'中位数候选人'=diff时，对于每一个Xi,找到比（Xi+diff）小

的X元素并累加即可，可以知道，假如diff是中位数，并且k是偶数，那么在diff之前应该最多有（k/2-1）个数才行，当然diff有重复时在它之前也可能少于（k/2-1）个数，故此时判断发现比diff小的数的个数小于等于（k/2-1），有可能diff过小，也有可能
正好就是中位数，所以将lb=mid，反之ub=mid,最终中位数取值范围是[lb,mid),缩小范围取lb即可。
若k偶数，在diff之前的应该最多有（k/2）个数才行，接下来的判断同理。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N_MAX = 100000;
typedef unsigned long long ull;
int X[N_MAX],N,m;
bool C(ull mid) {//比mid小的元素小于m/2个，那么mid偏小，也许还可以再大一点
    ull smaller_num = 0;
    for (int i = 0; i < N;i++) {
        smaller_num += lower_bound(X + i + 1, X + N, X[i] + mid)-(X+i)-1;
    }
    if(m&1)return smaller_num <= m/2;//返回true时，说明mid也许还可以大一点，也许mid已经是中位数了
    else return smaller_num < m / 2;
}

int main() {
    while (scanf("%d",&N)!=EOF) {
        for (int i = 0; i < N; i++) {
            scanf("%d",&X[i]);
        }
        sort(X, X + N);
        ull lb = 0, ub = *max_element(X, X + N) - *min_element(X,X+N)+1;
        m = N*(N - 1) / 2;
        while (ub - lb > 1) {
            ull mid = (ub + lb) / 2;
            if (C(mid))lb = mid;
            else ub = mid;
        }
        printf("%lld
", lb);
    }
    return 0;
}