$MedianPyramidHard$Median Pyramid Hard

$最初想法$最初想法

每次往上走, 最小值 与 最大值 都不会往上传, 于是就以为每次将最大值最小值去掉就好了, 即输出中位数…

$错因:$错因: 往上走时, 可能有数字重复地往上走, 出现了重复, 每次上去的就不一定是极值了.

$正解部分$正解部分

二分答案,
设二分出的答案为 $mid$mid,
则将原来的三角形中 大于等于 $mid$mid 的数字设为 $1$1, 其余设为 $0$0 .

$规律:若存在两个相邻的相同数字,则往上将继续出现两个相同数字相邻的形势.$规律:若存在两个相邻的相同数字,则往上将继续出现两个相同数字相邻的形势.

$Luogu$Luogu 题解上的图.

观察图可知, 哪种连续的数字离中轴较近, 则第一层为那种数字 .

于是只需要 $O\left(N\right)$O(N) 判断哪种数字离中轴最近即可 .

加上二分 总时间复杂度 $O\left(NlogN\right)$O(NlogN) .

$特殊情况:$特殊情况:

同样是 $Luogu$Luogu 题解上的图

这个时候没有连续的 $0$0 或 $1$1, 只需要看第一个元素是什么就可以了.

$实现部分$实现部分

$check函数:$check函数:

判断时可以不需要从左向右不断取 $\min$min 求最小值 .

可以直接从小到大枚举距离, 若有连续的数字, 直接返回即可,
若始终没有连续的数字, 为特殊情况, 特殊处理.

$左右端点的移动:$左右端点的移动:

• 若第 $1$1 层为 $1$1, 说明 真正答案 大于等于 $x$x, 需要将二分左端点右移.
• 反之 右端点 左移.

#include<bits/stdc++.h>
#define reg register

const int maxn = 2e5 + 5; //!

int N;
int A[maxn];
int B[maxn];

bool chk(int x){
        for(reg int i = 1; i <= 2*N-1; i ++) B[i] = (A[i]>x);
        for(reg int d = 1; d < N; d ++)
                if((B[N+d-1]&&B[N+d]) || (B[N-d+1]&&B[N-d])) return 1;
                else if(((!B[N+d-1])&&(!B[N+d])) || ((!B[N-d+1])&&(!B[N-d]))) return 0;
        return B[1];
}

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= 2*N-1; i ++) scanf("%d", &A[i]);
        int l = 1, r = 2*N-1;
        while(l < r){
                int mid = l+r >> 1;
                if(chk(mid)) l = mid + 1;
                else r = mid;
        }
        printf("%d\n", l);
        return 0;
}

$WhyWa?\downarrow$Why Wa?↓

#include<bits/stdc++.h>
#define reg register

const int maxn = 2e5 + 5; //!

int N;
int A[maxn];
int B[maxn];

bool chk(int x){
        for(reg int i = 1; i <= 2*N-1; i ++) B[i] = (A[i]>=x);
        for(reg int d = 1; d < N; d ++)
                if((B[N+d-1]&&B[N+d]) || (B[N-d+1]&&B[N-d])) return 1;
                else if(((!B[N+d-1])&&(!B[N+d])) || ((!B[N-d+1])&&(!B[N-d]))) return 0;
        return B[1];
}

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= 2*N-1; i ++) scanf("%d", &A[i]);
        int l = 1, r = 2*N-1;
        while(l < r){
                printf("%d %d\n", l, r);
                int mid = l+r >> 1;
                if(chk(mid)) l = mid;
                else r = mid - 1;
        }
        printf("%d\n", l);
        return 0;
}