安徽师大附中%你赛day4T1 金字塔解题报告

金字塔

题目背景：

(Zdrcl)带着妹子们来到了胡夫金字塔周边旅游，发现这里正在进行一个有关金字塔的游戏

题目描述：

游戏规则如下：

1、这里的金字塔是一个 (N) 阶的二维金字塔。

2、把金字塔的每一层从上往下从 (1) 到 (N) 顺次标号，对于第 (i) 层，有 (2*i-1) 个格子，且第 (i) 层的格子比第 (i+1) 层少的两个格子恰好是第 (i+1)层两端的格子。（如不理解，可参考下图）

一个 (4) 阶的金字塔

3、游戏的主办方在第 (N) 层的 (2×N-1) 个格子中写了一个 (1) ~ (2×N-1) 的排列。他希望你填上剩下的所有格子：对于第 (1) ~ (N-1) 层的所有格子上的数，应该等于这个格子左下方，正下方和右下方格子上所填的三个数的中位数。

4、游戏的主办方又觉得刚才的想法非常不(sha)行(diao)，因为如果那样的话，选手们要填的格子可能会非常多。所以，他只要求你告诉他第一层的那一个数是什么就行了。Zdrcl 想在妹子面前展现自己博学的形象，可是他又不愿自己亲手去做，于是他向在考场上的你发出了求助。你能帮助 Zdrcl么？帮助了他的话，他就会给你 100 分作为奖励哦！

输入输出格式

输入格式：

第一行一个正整数表示 (N)。

第二行有 (N×2-1) 个数表示主办方在最后一行填的数是什么。（注：保证给你的数是 (1) ~ (N×2-1) 的排列）

输出格式：

一行一个整数表示答案。

说明：

对于 30%的数据： (N ≤ 2*10^3)

对于 50%的数据： (N ≤ 8.5*10^3)

对于 100%的数据： (N ≤ 1*10^6)

对于 50%的数据，排列随机，在各测试点中均匀分布。

二分答案题，没看出来

基本算是套路吧，二分顶点，然后大于它的置1，反之置0

然后手玩

发现0101010类似的是每一层取反

11或00是一直向上走相当于屏障

于是我们可以从中间往左右两边走，第一次碰到的00或11就是顶

因为是奇数，所以不可能距离相等

如果一直是01，按层数算一算就行了

Code:

#include <cstdio>
const int N=2e6+10;
int a[N],d[N],n;
bool check(int m)
{
    for(int i=1;i<n<<1;i++) d[i]=a[i]>m;
    int l=-1,r=-1;
    for(int i=n-1;i;i--)
    {
        if(d[i]^d[i+1]) continue;
        l=i;break;
    }
    for(int i=n+1;i<n<<1;i++)
    {
        if(d[i]^d[i-1]) continue;
        r=i;break;
    }
    if((!~l)&&(!~r)) return d[n]^(n-1&1);
    if(!~l) return d[r];
    if(!~r) return d[l];
    return n-l>r-n?d[r]:d[l];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n<<1;i++) scanf("%d",a+i);
    int l=1,r=(n<<1)-1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))
            l=mid+1;
        else
            r=mid;
    }
    printf("%d
",l);
    return 0;
}

2018.8.16

安徽师大附中%你赛day4T1 金字塔 解题报告