---
# System prepended metadata

title: 题解：中位数金字塔
tags: [题解, ' 算法']

---

---
tags: 题解, 算法,
---

# 题解：中位数金字塔

在原题的生成上一层的方法中，能发现一个关键的特点，如果某处连续出现两个相同的数，那么在这两数之上的层也一定是这两个数。

再做一下推广，如果相邻两数较小一个是p，较大的是q，那么在这两数之上的一定大于等于p小于等于q。

结合以上两个特性我们可以来一波二分的骚操作。

假定一个整数m，把原金字塔上的数字，小于等于m的转为0，大于m的转为1，通过求这个金字塔塔顶的数字，如果是0就知道是小于等于m，如果是1就是大于m，于是可以通过二分m的值来求解。

对于一个01组成的数组，怎么快速求解塔顶的数字呢？我们知道，如果某处连续两个相同的数，那么在这两数之上也一定是这两个数，那么，如果这两个数在塔尖的左边，那么比它们更左的数字不会影响最终结果，同理右则也是，于是我们要求的是以下4种情况

```
00101...0101...10100
00101...0101...01011
11010...0101...10100
11010...0101...01011
```

我们拿其中一种来做一下金字塔演变

```
00000010...
00000101...
00001010...
00010101...
00101010...
```

同样地，如果有一侧是1，那上边就越来越多的1，也就是说，塔尖靠近哪个端点，最后就会成为那个端点的值（距离相等的时候两端点必然会是同0或同1），也就是说，我们可以以$O(n)$的复杂度判断塔尖是0还是1。

于是加上二分m，我们便可以以$O(nlogn)$的复杂度算出塔尖上的数字了。