Construct the Binary Tree

题意

给你n个结点，问是否可以构造成一个各结点深度之和为d的二叉树，如果可以输出YES和每个结点的父结点编号，如果不可以输出NO。根结点的编号固定为1

分析

这题很明显是个构造题，一向构造题弱项的我，写了3个小时也没有写出来，不过在参考了别人的博客之后，知道了怎么样能够更好的实现。这题的思路，如果让用手模拟的话很简单，但是要用代码来描述就比较困难了，所以也可以算是模拟算法题目。

我参考了这篇博客：传送门
图片说明
我们知道n个结点，构成深度之和最小的是完全二叉树，构成深度最大的是一条链。如果给定的d小于完全二叉树，或大于一条链的深度之和，则无法构成一个树，否则就一定可以。
我们将完全二叉树一步一步的向链进行转化，可以发现，只要不是链，我们总可以找到一个叶结点(除链上的最下面一个叶结点)。所以我们就是循环找到一个叶结点一步一步往下移动，也就是深度之和会逐步+1，直到变成d。
具体的做法就是上面图片所示，其中红色部分是准备转换成链的部分。每次是找非链上编号最大结点开始往下移动，一直移动到最底端，使得链长+1，然后再找非链上编号最大的下一个结点开始往下移动。

AC 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 5e3+10;
int dp[maxn],fa[maxn],list[maxn],in_list[maxn];
//保存结点深度，结点的父结点，某个深度链上结点是谁，某个结点是否在链上
int T,n,d;
void fun(){
    memset(dp,0,sizeof dp);
    memset(fa,0,sizeof fa);
    memset(list,0,sizeof list);
    memset(in_list,0,sizeof in_list);
    int sum = 0,mxdp = 0;
    for(int i = 2;i<=n;i++){
        fa[i] = i/2;
        dp[i] = dp[fa[i]]+1;
        sum += dp[i];
        mxdp = max(mxdp,dp[i]);
    }
    if(d < sum || d > n*(n-1)/2) { //不满足的情况
        puts("NO");
    }else{
        puts("YES");
        int cur = n;
        while(cur){ //记录每一深度链上结点编号
            list[dp[cur]] = cur;
            in_list[cur] = 1;
            cur = fa[cur];
        }
        for(int i = n;i>=1;i--){
            if(in_list[i]) continue; //链上结点不可移动
            while(dp[i] <= mxdp && sum < d){
                fa[i] = list[dp[i]];
                dp[i]+=1;
                sum +=1;
                if(dp[i] >mxdp){ //已经把新来的结点加在了最底端了。
                    mxdp = dp[i];
                    list[dp[i]] = i;
                    in_list[i] = 1;
                    break;
                }
            }
        }
        for(int i = 2;i<=n;i++) printf("%d ",fa[i]);
        puts("");
    }
}
int main(){
    cin>>T;
    while(T--){
        scanf("%d %d",&n,&d);
        fun();
    }

    return 0;
}