首页 > 代码库 > UVA 10821 - Constructing BST(贪心构造)
UVA 10821 - Constructing BST(贪心构造)
UVA 10821 - Constructing BST
题目链接
题意:有1 - n的数字,要构造一棵高度不超过h的BST,并且要字典序最小的,输出序列
思路:贪心构造,既然字典序最小,那么每个子树的根都要尽量小,那么也就是右子树尽量填满,按照这个策略去dfs构造即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n, h; void dfs(int s, int n, int h) { if (h == 0 || n == 0) return; int tmp = max(0, n - (1<<(h - 1))); printf(" %d", s + tmp + 1); dfs(s, tmp, h - 1); dfs(s + tmp + 1, n - tmp - 1, h - 1); } int main() { int cas = 0; while (~scanf("%d%d", &n, &h) && n || h) { printf("Case %d:", ++cas); if ((1<<h) - 1 < n) { printf(" Impossible.\n"); continue; } dfs(0, n, h); printf("\n"); } return 0; }
UVA 10821 - Constructing BST(贪心构造)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。