【AT2165】Median Pyramid Hard

题目

题目链接：https://www.luogu.com.cn/problem/AT2165
给出一个 (n) 层的方格金字塔,自顶向下依次标号为第 (1) 到第 (n) 层。
其中第 (i(1 le i le n)) 层有 (2i − 1) 个方格。（具体形态见下面的图）
第 (n) 层有一个 (1) 到 (2n-1) 的排列,其他层的数字按以下规则生成：方格 b 中填写的整数,是方格 b 正下方,左下方和右下方方格中所写整数的中位数。
现在给出第 (n) 层的数字，请你求第一层的数字。

思路

注意下文的 (n) 等于原题中 (2n-1)。
可以二分答案，然后套路性装换为 (01) 序列。
假设转换为 (01) 序列之后，离中间最近的相邻两个数字相同的是位置 (i)。不妨设 (frac{n}{2} leq i) 且 (a[i]=a[i+1]=1)。
那么显然上一行的位置 (i) 和 (i+1) 均是 (1)，而且位置 (i-1) 也应该是 (1)，否则必然有 (a[i-1]=a[i-2]=0)，那么就不满足 (a[i]) 与 (a[i+1]) 是最接近中间点的。
所以第一行的值就是距离 (frac{n}{2}) 最近的相邻数字相等的数值。因为有奇数列且每一个位置均为 (01)，所以不会出现距离相等的情况。
但是有一种特殊情况，就是相邻数字均不相等，那么第一行数值就是最后一行第一个位置的数值。
如果第一行为 (1) 说明答案不小于 (mid)，否则答案小于 (mid)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=200010;
int n,l,r,mid,a[N];

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

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