Median (二分答案 + 二分查找)

Median

题意:

有N个整数,计算两两不同的整数间的差值,然后找到差值中的中位数.

思路:

二分答案 + 二分查找

题目数据范围是xi <= 1e9,N <= 1e5;如果直接暴力1e10的复杂度必爆;1e9数据需要longlong处理;

二分枚举中位数的可能值,然后二分查找满足条件的个数;

这里我们找的个数是比中位数小的数的个数,这个式子中一共有n * (n - 1) / 2个数 那么偶数个的中位数就是 n * (n - 1) / 4 ,奇数就是n * (n - 1) / 4 + 1;

直接给每个值加上中位数,然后upper_bound统计有多少个比中位数值小的数即可,最后看是否满足一半的个数即可

根据取大取小,合理使用lower_bound和注意往那一边进行搜索

AC代码:
取大的

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
ll n, m;

bool check(int x){
    ll sum = 0;
    for(int i = 0;i < n;i ++){
        int pos = n - (upper_bound(a,a + n,a[i] + x) - a);
        sum += pos;
    }
    return sum <= m;
}

int main(){
    while(~scanf("%d",&n)){
        for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
        sort(a,a + n);
        m = n * (n - 1) / 4;
//        if(m & 1) m = m / 2;
//        else m = m / 2;
        int l = -1,r = a[n - 1] - a[0];
        while(l < r){
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n",l);
    }
    return 0;
}

取小的

# include <iostream>
# include<cstdio>
# include <algorithm>
 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
ll n, m;
 
bool check(int x){
    ll sum = 0;
    for(int i=0; i<n-1; ++i){ //统计有多少个比x小
        int pos = upper_bound(a+i, a+n, a[i]+x)-a;
        sum += pos - i - 1;
        if(sum >= m)
            return true;
    }
    return false;
}

int main(){
    while(~scanf("%lld",&n)){
        for(int i=0; i<n; ++i)
            scanf("%d",&a[i]);
        ll tmp = n*(n-1)>>1;
        if(tmp&1)
            m = (tmp>>1)+1;
        else
            m = tmp>>1;
        sort(a, a+n);
        int l=0, r=a[n-1]-a[0], mid;
        while(l<r)
        {
            int mid = (l + r)>>1;
            if(check(mid))
                r = mid;
            else
                l = mid+1;
        }
        printf("%d\n",r);
    }
    return 0;
}