闲扯

今天模拟的题，应该是挺简单的二分和贪心，就是没想出来，我好弱啊

顺便ORZ聚聚BLUESKY007，踩爆我了

思路

今天发现中位数性质如此优秀

二分最后塔顶的数，大于等于它的数变为1，小于它的数变为0，然后发现当有两个相邻的0或1在一起的时候，就会不会被去掉，会向上移动，利用这个性质，可以搞出快速判断的方法

就是找到距离中轴线最近的连续两个0或1，如果是0，就证明小于它的数在塔顶，否则证明大于等于它的数在塔顶，然后二分

注意判断没有任何一组的情况（即01相间），此时最边缘的会在顶端，特判一下

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int a[200100],n;

bool check(int x){

    for(int i=0;i<=n-1;i++){

        if((a[n-i]<x&&a[n-i-1]<x)||(a[n+i]<x&&a[n+i+1]<x))

            return false;

        if((a[n-i]>=x&&a[n-i-1]>=x)||(a[n+i]>=x&&a[n+i+1]>=x))

            return true;

    }

    return a[2*n-1]>=x;

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=2*n-1;i++){

        scanf("%d",&a[i]);

    }

    int l=1,r=2*n-1,ans=0;

    while(l<=r){

        int mid=(l+r)>>1;

        if(check(mid))

            l=mid+1,ans=mid;

        else

            r=mid-1;

    }

    printf("%d\n",ans);

    return 0;

}