NOIP 提高 2011 第一轮 第 35 题：完善程序（大整数开方）第 1 空

题目

2.（笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列 $7,2,12,1,10,5,15,3$，下图就是一棵对应的笛卡尔树。现输入序列的规模 $n(1≤n<100)$ 和序列的 $n$ 个元素，试求其对应的笛卡尔树的深度 $d$（根节点深度为 $1$），以及有多少个叶子节点的深度为 $d$。

![](https://cdn.luogu.com.cn/upload/image_hosting/84hi4zrg.png)

#include<iostream>
using namespace std;
const int SIZE=100+5;
const int INFINITY=1000000;
int n,a[SIZE],maxDeep,num;
void solve(int left,int right,int deep)
{
int i,j,min;
    if(deep>maxDeep){
        maxDeep=deep;
        num=1;
    }
    else if(deep==maxDeep)
              ①     ;
    min= INFINITY;
    for(i=left;i<=right;i++)
        if(min>a[i]){
            min=a[i];
                ②    ;
        }
    if(left<j)
            ③   ;
    if(j<right)
           ④     ;
}
int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    maxDeep=0;
    solve(1,n,1);
    cout<<maxDeep<<' '<<num<<endl;
    return 0;
}

①处应填（ ）

答案

num++

题解

考点定位

本题（完善程序「笛卡尔树」第①空）考「最大深度计数」,对应大纲 4.3.3 树结构（难度【4】）。

程序思路：递归找区间最小值作根（最小堆），分左右递归求笛卡尔树深度及最深叶子数。

解题过程

①处在深度超过/等于当前最大时的分支：

``cpp else if (deep == maxDeep) num++; ``

（deep>maxDeep 时已置 num=1；并列时叶子数 +1。）答案：num++。

易错提醒

① maxDeep/num 联动：更深则重置计数、等深则累加；② 递归按最小值分割，保证堆性质 + 中序=原序列。