CodeForces - 1311E(Construct the Binary Tree)

题目链接：http://codeforces.com/contest/1311/problem/E

题意：

思路：

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5001;

int num[MAXN], tree[MAXN][MAXN], ans[MAXN];
int check(int n, int d)
{
    int di = (n - 1) * n / 2 - d;
    if (di < 0) return 0;
    int cur = 2, k;
    for (int i = n; i >= 1 && di; --i)
    {
        k = min(i - cur, di);
        di -= k;
        num[cur]++;
        ans[i] = tree[cur - 1][(num[cur] + 1) / 2];
        tree[cur][num[cur]] = i;
        if (num[cur] == (1 << (cur - 1))) cur++;
        if (i == cur) break;
    }
    if (di > 0) return 0;
    else return 1;
}
inline void solve()
{
    int n, d; cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {
        tree[i][1] = i;
        num[i] = 1;
        ans[i] = i - 1;
    }
    if (check(n, d))
    {
        cout << "YES" << endl;
        for (int i = 2; i <= n; i++) cout << ans[i] << " ";
        cout << endl;
    }
    else
        cout << "NO" << endl;
}
int main()
{
    int T = 1; cin >> T;
    for (int i = 0; i < T; ++i) solve();
    return 0;
}