ABC107D Median of Medians

前言

ABC即AtCoder Beginner Contest.
(感觉AtCoder的题目的题目名都好有趣啊…可惜不会做)

题目描述

分析

容易发现,如果这个数要成为序列的median,至少要有\lfloor \frac {len} {2}\rfloor+1个元素小于等于它。
但是我们并找不到什么性质可以直接分析这个序列得到答案。
因此考虑二分查找,二分这个中位数,设所有区间中位数个数为tot=N\ast (N+1)/2,那么就是要找至少有tot+1个区间的中位数小于等于它的最小的数。
问题就是如何确定这个中位数小于等于当前二分的答案x的区间个数。
我们可以这样操作:在原序列基础上构造一个新序列,原序列中大于x的变成-1,小于等于x的变成1.那么问题就转化为有新序列多少个区间的元素之和大于等于tot+1.更进一步,我们对新序列累加前缀和,设这个前缀和序列是S,那么问题就是找S中,有多少对0\le i < j\le N,满足S_j > S_i.看到了吧,其实就是一个二位偏序问题,或者说“顺序对”。那么我们只需要归并排序就可以解决了。
复杂度:O(Nlog^2N)

核心代码

细节还是有一点点的…

typedef int IntAr[MAXN];
typedef long long LL;

int N;
IntAr A, B, C, D;
LL tot;

int main() {
    using FastIO::read;
    read(N);
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
    memcpy(B, A, sizeof(int) * N);
    std::sort(B, B + N);
    int lb = -1, mid, ub = std::unique(B, B + N) - B - 1;   // 直接在去重后的原序列上二分
    LL pos = (LL(N) * (N + 1) >> 2) + 1;
    for (; ub - lb > 1; ) { // (lb, ub]
        mid = lb + ub >> 1;
        if (count(B[mid]) >= pos) ub = mid;
        else lb = mid;
    }
    printf("%d\n", B[ub]);
    return 0;
}

LL count(int key) {
    C[0] = 0;
    for (int i = 1; i <= N; i++) C[i] = C[i - 1] + (A[i - 1] > key ? -1 : 1);   // 预处理出前缀和序列
    tot = 0;
    merge(0, N + 1);
    return tot;
}

void merge(int l, int r) {
    // merge sort interval [l, r)
    if (r - l <= 1) return;
    int mid = l + r >> 1;
    merge(l, mid);
    merge(mid, r);
    int i, j, k;
    for (i = l, j = mid, k = l; i < mid && j < r; )
        if (C[i] < C[j]) {
            D[k++] = C[i++];
            tot += r - j;
        }
        else D[k++] = C[j++];
    for (; i < mid; ) D[k++] = C[i++];
    for (; j < r; ) D[k++] = C[j++];
    memcpy(C + l, D + l, sizeof(int) * (r - l));
}

总结

比赛的时候一直以为这种题目可以直接找出某些性质O(N)出答案。事实证明想得还是简单了…二分查找是一个十分有用的武器,一定要熟练掌握。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注