[AGC006D] Median Pyramid Hard 题解

题目链接：[AGC006D] Median Pyramid Hard

题意：

给出一个 $N~(1 \le N \le 10^5)$ 层的方格金字塔，自顶向下依次标号为第 $1$ 到第 $N$ 层。

其中第 $i~(1 \le i \le N)$ 层有 $2i - 1$ 个方格（具体形态见下面的图）

第 $N$ 层有一个 $1$ 到 $2N-1$ 的排列，其他层的数字按以下规则生成：

• 方格 $b$ 中填写的整数，是方格 $b$ 正下方、左下方和右下方方格中所写整数的中位数。

现在给出第 $N$ 层的数字，请你求第一层的数字。

考虑二分最上层这个数 $\ge x$，然后令 $\ge x$ 的数为 $1$ ，$<x$ 的的数为 $0$ 。

那么原题可以转化为，每次操作对于相邻的三个数，

如果 $1$ 的个数 $\ge 3$ 则为 $1$ ，否则为 $0$ ，最终最上面的那个数是 $0$ 还是 $1$ 。

这样问题就变成了 $0,1$ 序列如何快速判断了，接下来就是找规律了，请参考 link 或者下图

时间复杂度 $\mathcal{O}(n \log n)$ ，当然这题还有 $\mathcal{O}(n)$ 的解法，也是基于这一规律的。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

int n, a[N], b[N];
bool check(int x)
{
    rep(i, 1, n * 2 - 1) b[i] = (a[i] >= x);
    rep(i, 0, n - 2)
    {
        if(b[n + i] == b[n + i + 1]) return b[n + i];
        if(b[n - i] == b[n - i - 1]) return b[n - i];
    } return b[1];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 1, n * 2 - 1) cin >> a[i];
    int l = 1, r = (n << 1) - 1;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        check(mid) ? l = mid : r = mid - 1;
    }
    cout << l << '\n';
    return 0;
}

---

参考文献

就是上面那个link。

---

题外话：

没图片，但是推歌。