Median Pyramid Hard:二分 trick 加上性质观察题。
trick
我们可以二分值域,然后把大于等于它的数标记成 \(1\),其他标记为 \(0\)(有些题需要标记成 \(-1\) ),然后根据这个来 check 方案是否可行,这通常通过判断某个数是否是 \(1\) 来实现。本质上其实就是 check 大于等于它的数能否成为答案(大于等于它的数为 \(1\))。常用于查找中位数、第 \(k\) 个数,以及大小关系只注重两种(比如只区分大于 \(7\) 和小于 \(7\) ,而大于 \(7\) 的数之间的大小无关的情况)。
这道题就是二分塔顶,check 大于等于它的数能不能成为塔顶,把大于等于它的数设为 \(1\),其他设为 \(0\) 。
观察性质
那么这题显然对应着“大小关系只注重两种”的用途,接下来考虑如何 check。
观察到一个位置下面的三个数只可能是这些情况:
0 0 0 => 0
0 0 1 => 0
0 1 0 => 0
0 1 1 => 1
1 0 0 => 0
1 0 1 => 1
1 1 0 => 1
1 1 1 => 1
然后我们手搓样例,继续观察:
sample1:
1
1 1 1
0 1 1 1 0
0 0 1 1 0 1 0
sample2:
1
0 1 1
0 1 0 1 1
0 1 0 1 0 1 1
可以观察到,当 \(1\) 或者 \(0\) 形成一段长度大于等于 \(2\) 的连续区间时,他们就能不断上升,直到塔顶。因为结果与这个区间的长度基本无关,所以我们只取最靠近中间的两个即可。
如果有一段区间既不是 \(1\) 的连续区间,也不是 \(0\) 的区间呢?那么它一定是 \(01\) 交替的区间。而 \(01\) 交替的区间又正好可以让某一段连续区间不断攀升(起到辅助作用)。因此,我们只要找到离中间最近的一段交替区间即可,它的数字就是塔顶的数字。
可以证明,一定没有一个 \(1\) 的连续区间和一个 \(0\) 的连续区间,使他们到中间的距离相等,例子如下:
1 1 1 * * * 0 0 0
此时星号里必须填入一个 \(01\) 交替,以 \(0\) 开头,以 \(1\) 结尾的串。但这显然不成立,因此没有这种情况。
还有一种特殊情况:所有 \(01\) 都是交替出现,找不到满足要求的 \(01\) 区间。很容易发现这种情况的答案就是最底层第一个数的数字(手动模拟一下就可以了)。那么特判一下就可以了。
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int a[200005],n,f[200005];
bool check(int p)
{
for(int i=1;i<=2*n-1;i++)f[i]=(a[i]>=p);
for(int i=0;i<=n-2;i++)
{
if(f[n-i]==f[n-i-1])return f[n-i];
if(f[n+i]==f[n+i+1])return f[n+i];
}
return f[1];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=2*n-1;i++)cin>>a[i];
int l=1,r=2*n-1,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
标签:二分,Atcoder,Pyramid,int,题解,01,区间,大于,check
From: https://www.cnblogs.com/zhr0102/p/18385258