Poj 3579: Median

poj3579.md

Poj 3579: Median

題目

分析

很明顯的，這題不是要你排序然後輸出 median… 所以解法的時間複雜度必優於 O(n^2)

這題既然歸類在二分搜底下，那就從二分搜來思考吧。

很直覺的想法就是，對差進行二分搜，而判斷函式為此數作為 median 是否太大， 即 median 是否 > m

正負相關性判定

bool C(m) = median 是否 > m

而 C(s) 表是

0 0 0 0 1 1 1

這種形式，而我們的目標是尋找 最後一個 0 在哪

---

實作時，改為計算 >= m 的差的個數，是否 <= 所有差的個數 / 2

如果序列已排序，計算個數時，可用 lower_bound

上下界判定

使用 (lb, ub] :

lb: 足夠小，並使 C(lb) = false 的數，即 0

ub: 足夠大，並使 C(ub) = true 的數，即最大的差

其它

此解法的時間複雜度為 二分搜 乘上 n 個 lower_bound ，即 O(lg(ub - lb) * n * lg(n))，代入值，約為 50,000,000 小於 O(n^2) 的 10 ^ 10

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int N, C_2;
int X[100000];

bool C(int m) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        cnt += X + N - lower_bound(X + i + 1, X + N, X[i] + m);
    }

    return cnt <= C_2 / 2;
}

int solve() {
    C_2 = N * (N - 1) / 2;

    sort(X, X + N);

    int lb = 0;
    int ub = X[N - 1] - X[0];

    // (lb, ub]
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (C(mid)) ub = mid;
        else lb = mid;
    }

    return lb;
}

int main() {
    while (scanf("%d", &N) != EOF) {
        for (int i = 0; i < N; i++)
            scanf("%d", &X[i]);

        printf("%d\n", solve());
    }

    return 0;
}