[??记录]AT2165 [AGC006D] Median Pyramid Hard
command_block
·
·
个人记录
题意 ： 给出一个 N 层方格金字塔，自顶向下依次标号为第 1 到第 N 层。
其中第 i 层有 2i − 1 个方格。（具体形态见图）
第 N 层有一个 1 到 2N-1 的排列，其他层的数字按以下规则生成：方格 b 中填写的整数，是方格 b 正下方，左下方和右下方方格中所写整数的中位数。
现在给出第 N 层的数字，求第一层的数字。
------------
中位数和大小比较有关，考虑二分答案。
若数 $\leq mid$ 则设为 $0$ ，否则设为 $1$。
则金字塔的生成方法可以改为 ： 若下方的三个格子中 $1$ 多则填 $1$ ，否则填写 $0$。
若最终第一层的数字为 $0$ 则表示答案 $\leq mid$ ，否则 $>mid$。
现在问题变为快速求解 $01$ 金字塔。
这个问题似乎很有规律，手玩可以发现，若有两个相邻的 $0/1$ ，就会一直向上传递到顶。
（不懂手玩……规则简单/偏组合就手玩，复杂就分析？）
而且，两个的相邻 $0/1$ 会吞噬周围孤立的 $0/1$。
综合上述两条，不难发现，答案是距离中心最近的对子的值。
由于底端长为奇数，可以证明不会出现两个距离中心一样近的对子。
然而，一种特殊情况是没有任何对子，特判掉就好了。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 200500
using namespace std;
int n,a[MaxN];bool b[MaxN];
bool chk(int lim)
{
for (int i=1;i<=2*n-1;i++)b[i]=(a[i]>=lim);
int dis=n,fl;
for (int i=1;i<n;i++)
if (b[i]==b[i+1]&&n-i<dis)
{dis=n-i;fl=b[i];}
for (int i=n+1;i<=n*2-1;i++)
if (b[i-1]==b[i]&&i-n<dis)
{dis=i-n;fl=b[i];}
return (dis==n) ? b[1] : fl;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n*2-1;i++)scanf("%d",&a[i]);
int l=1,r=n*2-1,mid;
while(l<r){
mid=(l+r+1)>>1;
if (chk(mid))l=mid;
else r=mid-1;
}printf("%d",l);
return 0;
}
```