题目

3、排列变换–1200
时间限制： | 空间限制：
题目描述：
给出一个大小为 的排列 ,Convert it to a rooted binary tree according to the following rules：
1.The current paragraph（初始时是 中所有数）The number of the largest value in the current subtree（Initially it is the whole tree）the number of the root;
2.All numbers to the left of the maximum position in this segment form the left subtree,Process recursively according to the rules;
3.All numbers to the right of the maximum position in this segment form the right subtree,Process recursively according to the rules.
比如说,排列 The composed binary tree is like this：
root,Its left son is 号,右儿子是 号; No. Left son is 号,右儿子是 号; No. Left son is 号,右
儿子是 号.
Request the depth of each point in the tree（That is, how many edges are there on the simple path from this point to the root,特殊地,根的深度为0）.
输入格式：
第一行仅有一个正整数 （ ）,表示测试数据的组数.
接下来有 组测试数据：
第一行仅一个正整数 （ ）,Indicates the arrangement size;
The second row has a size of 的排列 用空格隔开.
输出格式：
对于每组测试数据,输出一行 个整数用空格隔开,分别表示 号点的深度.

思路

递归

代码实现

#include<bits/stdc++.h>
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;
}