题目链接

Median POJ - 3579

思路

$$ 二分求解。\\\\1.假设有(C_n^2 + 1)/2对线段长度>=X\\\\2.如果满足则缩小X\\\\3.否则增大X\\\\check()时类似尺取，记录一个当前右端点能符合的最左端点。\\\\笔者long long g = 1LL * n * (n - 1) / 2;写成了n*(n-1)/2\\\\这里int爆炸了 $$

时间复杂度

$$ O(max(Nlog(N), Nlog(max(x_i)))) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

int n;
int a[MAXN];

bool check(int mid) {
    long long g = 1LL * n * (n - 1) / 2;
    g++;
    g /= 2;
    long long cnt = 0;
    int l = 1;
    for (int i = 1; i <= n; i++) {
        while (l <= i && (a[i] - a[l] > mid)) {
            l++;
        }
        long long w = i - l;
        cnt += w;
    }
    return cnt >= g;
}

int main() {

    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
        }
        sort(a + 1, a + 1 + n);
        int l = 0, r = 1e9+10, ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}