题目链接：戳我
一看范围1e5，往二分上想。
可是再怎么也没有想到这个神仙的二分答案qwq
我们二分一个数x，设比他大的数为1，小于等于他的数为0。那么我们就可以把原来的那个转化成一个01塔。
然后我们可以通过实验发现，如果有连续的0或者1的话，它一定会向上面推进一格qwqwq。然后谁最先占领最上面的那个格子——如果是1，就是当前枚举的答案小了，反之则大。
所以我们直接寻找哪个连续两个或以上的数离中轴线更近qwq即可。
这样子时间复杂度是木有问题，二分一个log，查询的话最劣也是O(n)。
但是有一种例外，就是01交替分布，不存在两个或以上连续的。那我们就查不到了！
不过没有关系，这种特判一下即可。第一个是0的话最终上面的就是0，第一个是1的话最终就是1。（为什么？手动绘图一下即可）
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200010
using namespace std;
int n,l,r,mid;
int a[MAXN];
inline bool check_large(int x,int y)
{
if(a[x]>mid&&a[y]>mid) return true;
return false;
}
inline bool check_small(int x,int y)
{
if(a[x]<=mid&&a[y]<=mid) return true;
return false;
}
inline bool solve()
{
for(int i=0;i<n-1;i++)
{
if(check_large(n+i,n+i+1)||check_large(n-i,n-i-1)) return true;
if(check_small(n+i,n+i+1)||check_small(n-i,n-i-1)) return false;
}
if(a[1]<=mid) return false;
else return true;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n*2-1;i++) scanf("%d",&a[i]);
l=1,r=2*n-1;
while(l<r)
{
mid=(l+r)>>1;
if(solve()==true) l=mid+1;
else r=mid;
}
printf("%d\n",l);
return 0;
}
小蒻菜实在是没有想到这种神仙做法，表示自己还是太菜了qwqwq