AT2165 Median Pyramid Hard

时间:2022-05-20 21:04:16

题目链接:戳我

一看范围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