【题解】UVA10821 Constructing BST

5ab_juruo · 2022-02-18 22:23:04 · 题解

对于没有自平衡的二叉搜索树，给定节点数 n 和树高限制 h，要求构建字典序最小的排列，使得按照这个顺序插入该树后树高 \le h，或者说明不可能。

多组数据。

一道简单的贪心构造题。

显然，高度为 h 的二叉搜索树最多能容纳 2^h-1 个节点。为了使字典序最小，对于当前每个节点，看右子树最多能容纳多少节点（设为 x），除去最大的 x 个数，剩余的最大值就填在该节点。左右子树递归处理即可。

最后输出方案时，只需要输出该树的先序遍历即可，易证这样一定可以构建出期望的树。事实上不必真正建出这棵树，只需要递归的时候顺便输出即可。

输出格式比较恶心。

/* name: UVa10821
 * author: 5ab
 * created at: 22-02-18 22:01
 */
#include <iostream>
using namespace std;

typedef long long ll;

inline int my_max(int a, int b) { return (a > b)? a:b; }
void solve(int sp, int n, int h)
{
    if (!h || !n) return;
    int pos = my_max(n - (1 << (--h)), 0);
    cout << " " << sp + pos;
    solve(sp, pos, h), solve(sp + pos + 1, n - pos - 1, h);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, cid = 0;

    while (cin >> n >> k)
    {
        if (!n) break;
        cout << "Case " << ++cid << ":";
        if (n >= (1 << k))
            cout << " Impossible." << endl;
        else
        {
            solve(1, n, k);
            cout << endl;
        }
    }

    return 0;
}