1. 【NOIP2011】笛卡尔树

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

补全程序：

#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;
}

选择题：

1. ①处应填（ ）
   {{ select(1) }}

• num++
• return
• ++left
• --right

2. ②处应填（ ）
   {{ select(2) }}

• i=j
• j++
• j=i
• j--

3. ③处应填（ ）
   {{ select(3) }}

• solve(j,right,deep+1)
• solve(j+1,right,deep+1)
• solve(left,j,deep+1)
• solve(left,j-1,deep+1)

4. ④处应填（ ）
   {{ select(4) }}

• solve(left,j,deep+1)
• solve(j+1,right,deep+1)
• solve(j,right,deep+1)
• solve(left,j-1,deep+1)