AT2165 中位数金字塔 笔记

· · 题解

题目传送门

solution

我们需要求的是每组的中位数，所以记录大小关系是很重要的（废话。

对于一个数字 x，记录在塔底的数列中，每一个 a_i 是否小于等于 x，如果小于等于 x 则为 0，大于 x 则为 1，这样就得到了一个 01 序列。

以样例为例，当 x 为 3 时序列是 0,1,0,1,1,1,0。很明显下面的三个数有 110，001，111，000的可能。取中位数时，一定得到的是出现得多的数，然后在 110 中取到 1，001 中取到 0。

把这个性质向上推，就有一种情况：当 a_i，a_{i+1} 为 1，上一行的 i，i+1 也为 1。

可以知道只要一直往上推，直到塔尖，这个性质依然适用。那么有这么多的 11，00，只要谁离中间点最近，它就可以"走"到塔尖，塔尖的 01 值与它相等。

那怎样找到这个 x 呢？可以枚举。想到枚举，就可以想到二分。注意，我们应该用用数组下标（即数字组合）来二分才对。

code

#include <cstdio>
#include <cstring>
int N, Ans, A[200001], B[200001];

namespace S {
    inline bool Min(int w1, int w2, int d) {
        return A[w1] <= d && A[w2] <= d;
        //两个是否都是小于等于当前值 
    } 

    inline bool Max(int w1, int w2, int d) {
        return A[w1] > d && A[w2] > d;
        //两个是否都是大于当前值 
    }

    inline int check(int x) {
        int Mid = N / 2 + 1; //中间点（塔顶对于塔底数列是第几个）
        for(int i = 0; i < Mid - 1; i ++) {
            /*
               制作 01 序列：从中间往边上找有没有 00 或 11
               就可以找到最靠中间的两个相同的，像解释中那样
            */
            if(Max(Mid - i, Mid - i - 1, x) || Max(Mid + i, Mid + i + 1, x)) {
                return 1;
            }
            if(Min(Mid - i, Mid - i - 1, x) || Min(Mid + i, Mid + i + 1, x)) {
                return 0;
            }
        }
        return !(A[1] <= x);
        //特判没有 00 , 11 时的情况，此时易得塔顶应为第一个或最后一个 0 或 1
    }

    inline int read() { //读入优化 
        int cnt = 1, res = 0;
        char ch = getchar();
        while(ch < '0' || ch > '9') {
            cnt = ch == '-' ? -1 : 1, ch = getchar();
        }
        while(ch >= '0' && ch <= '9') {
            res = res * 10 + (ch ^ 48), ch = getchar();
        }
        return res * cnt;
    }

    inline void print(int x) {
        if(x < 0) putchar('-'), x = -x;
        x > 9 ? print(x / 10), putchar((x % 10) ^ 48) : putchar((x % 10) ^ 48);
    }

    inline void Erfen() { //二分寻找 x 作为候选答案
        int l = 1, r = N; //因为 N 已是 N * 2 - 1，所以 r 直接赋值为 N
        while(l < r) { //因为要求的是最后一个小于等于的，所以是用右标记查找
            int Mid = (l + r) / 2; //二分查找中的中间值
            int p = check(Mid); //判断塔顶答案是否比 x 大
            if(p == 0) {
                r = Mid;
            } else {
                l = Mid + 1;
            }
        }
        print(r); //找到答案，输出
    }
}
using namespace S;

int main(int argc, char const * argv[]) {
    memset(B, 127, sizeof(B)); //赋值为无穷大
    N = read() * 2 - 1; //读入 N 的值  
    for(int i = 1; i <= N; i ++) {
        A[i] = read();
    }
    Erfen(); //直接二分 
    return 0; //完美的结束 
}

tips

如果一个 11，00 都没有出现，要特判塔尖应改为最左边，还是最右边那个值？（想一想。