题目

3、排列变换–1200
时间限制： | 空间限制：
题目描述：
给出一个大小为 的排列 ，按如下规则将它转化为一棵有根二叉树：
1.目前这一段（初始时是 中所有数）中的最大值的编号为目前子树（初始时是整棵树）的根的编号；
2.所有在这一段中最大值位置左侧的数形成左子树，按照规则递归处理；
3.所有在这一段中最大值位置右侧的数形成右子树，按照规则递归处理。
比如说，排列 组成的二叉树是这样的：
号为树根，它的左儿子是 号，右儿子是 号； 号左儿子是 号，右儿子是 号； 号左儿子是 号，右
儿子是 号。
请求出每个点在树中的深度（即该点到根的简单路径上有多少条边，特殊地，根的深度为0）。
输入格式：
第一行仅有一个正整数 （ ），表示测试数据的组数。
接下来有 组测试数据：
第一行仅一个正整数 （ ），表示排列大小；
第二行有一个大小为 的排列 用空格隔开。
输出格式：
对于每组测试数据，输出一行 个整数用空格隔开，分别表示 号点的深度。

思路

递归

代码实现

#include
using namespace std;

const int maxn=100+10;
int t,n;
int a[maxn],h[maxn];
void search(int l,int r){
	if(r<l)return;
	int temp=0,t=0;
	for(int i=l;i<=r;i++){
		h[i]++;
		if(a[i]>temp){
			temp=a[i];
			t=i;
		}
	}
	search(l,t-1);
	search(t+1,r);
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(h,-1,sizeof(h));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		search(1,n);
		for(int i=1;i<=n;i++)printf("%d ",h[i]);
		printf("\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31