【二分】AT2165 Median Pyramid Hard

WeLikeStudying · 2022-02-15 13:54:35 · 题解

• 有比正解时间复杂度更优的线性解法！值得一看！

题意

• 题目链接。
• 给定一个数字金字塔，底层有 2n-1 个数，分别是 1 到 2n-1 的一个排列，逐次减 2，顶层有 1 个数。
• 每个方格内的数是正下，左下，右下的三个数的中位数。
• 求最上面方格的数字。

分析

• 首先可以二分答案，然后问题变成只有 0,1 的情况，然后我们就写个关于 0,1 的 O(n^2) 暴力求解找规律。
• 实验程序和探究结论。
• 通过这个实验程序的辅助，我们找到了 O(n) 判定 01 情况的做法，那么通过二分，我们也找到了 O(n\log n) 判定一般情况的做法，代码实现不算困难。
• 代码实现。

拓展

• 学过二分的都知道二分答案有个重要的思想：去二分化。
• 其大概意思就是二分虽好，可以大大简化问题，方便性质的发现，但是时间复杂度会增加一个 \log，有的时候跑一个 \log 未必轻松，所以我们可以先用二分找到一个问题的较好解法，然后根据这个性质，将二分改为扫描，尝试用另一种方法动态维护这个性质，复杂度就会降低一个 \log。
• 我们首先对输入进行计数排序，然后逐个从小到大加入，情况与 01 类似（可以理解成一堆 1，按照顺序逐个把它们变成 0）。
• 根据我们之前发现的性质，如果加入这个数字位置的 0 之后，第一次使得所有奇数位置上全都是 0，或者使得有两段连续的 0 比两段连续的 1 更靠近中间，那么这个数字就是答案。
• 这显然是可以均摊 O(1) 维护的，双指针维护最靠近中心的连续 1 的位置均摊复杂度是对的，开个数组维护奇数位置上的 1 的个数，每次答案的时候都 O(1) 更新最近的连续 0 的个数……总之都是基础的普及难度的操作。
• 说句实话，这么简单的线性方法，以各位的智商，想到是不困难的，但区别就在于愿意不愿意，虽然各位或许都比我强，但我仍然希望各位多思考，或许也有不一样的收获呢。
• 代码实现，代码实现也很简单。

再拓展

• 这篇提到的问题，为什么有的二分不能处理一般情况？题解似乎并没有用到排列的性质。
• 我给出的回答是：错误的原因是因为数据值域不连续，将数据离散化就可以了，为什么？