AGC006_D Median Pyramid Hard

图片搬运来源：官方

前言

如果没写过此比赛的B题，可先去解决B题，对此题会有一定帮助。
题目：https://agc006.contest.atcoder.jp/tasks/agc006_b
blog:https://www.cnblogs.com/Alseo_Roplyer/p/10189171.html

题面翻译
首先和此比赛B题一样，给你一个构造方法相同的金字塔，给你第n层填的数，求出第一层填的数。

思路
首先我们可以二分。
然后将>=mid的数记为1，反之记为0，然后判断第一层上的数为1还是0。然后我们利用B题的性质可得，如果第n层中心线两边的数其中一个和中心线上的数相同，那么第一层填的数就确定了。否则中心线上与其相邻的数一定不同，那么我们再看距中心线一格的两个格子与其周围的数的关系，如果相同那么第一层的数一定就为那两个格子上的数，否则再看距中心线两个的两个格子，如此递归下去。为什么呢？其实也很显然，我们不断从中心线向两边枚举，枚举到距中心线最近的相邻两数相同的位置，那么从中心线到这个位置一定是0,1交替的，那么这样的形状也会延续到上面一层，但是0,1会互换，但是那两个位置上的数不会改变，而到了上面一层，与他们相邻的位置上的数一定也与他们相同了，这就像每进行一轮，他们就会感染相邻的位置，那么如此反复就一定会到达中心线的位置。给一个图感受一下。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5;
int n;
int a[maxn*2+8],b[maxn*2+8];

int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

bool check(int k)
{
    for (int i=1;i<2*n;i++) b[i]=a[i]>=k;
    for (int i=1;i<n;i++)
	{
	    if ((b[n-i]&&b[n-i+1])||(b[n+i]&&b[n+i-1])) return 1;
	    if ((!(b[n-i]||b[n-i+1]))||(!(b[n+i]||b[n+i-1]))) return 0;
	}
    return b[1];
}

int main()
{
    n=read();
    for (int i=1;i<2*n;i++) a[i]=read();
    int l=1,r=2*n-1,ans;
    while(l<=r)
	{
	    int mid=(l+r)>>1;
	    if (check(mid)) l=mid+1,ans=mid;
	    else r=mid-1;
	}
    printf("%d
",ans);
    return 0;
}