将一系列给定数字插入一个初始为空的小顶堆H[]
。随后对任意给定的下标i
,打印从H[i]
到根结点的路径。
输入格式
每组测试第1行包含2个正整数N和M(≤1000),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式
对输入中给出的每个下标i
,在一行中输出从H[i]
到根结点的路径上的数据。数字间以1个空格分隔,行末不得有多余空格。
输入样例
1 2 3
| 5 3 46 23 26 24 10 5 4 3
|
输出样例
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include<stdio.h> #define MAXN 1001 #define MINH -10001 int H[MAXN], size; void Create(); void Insert(int X); int main() { int n, m, x, i, j;
scanf("%d %d", &n, &m); Create(); for (i = 0; i < n; i++) { scanf("%d", &x); Insert(x); } for (i = 0; i < m; i++) { scanf("%d", &j); printf("%d", H[j]); while (j > 1) { j /= 2; printf(" %d", H[j]); } printf("\n"); } return 0; } void Create() { size = 0; H[0] = MINH; } void Insert(int X) { int i;
for (i = ++size; H[i / 2] > X; i /= 2) H[i] = H[i / 2]; H[i] = X; }
|
测试点
1 2 3 4 5
| 测试点 提示 0 sample 调整到根、到中间位置,有不需要调整的元素 1 路径更长,交错,index从中间开始,有负数 2 最小N和M 3 最大N和M随机,元素取到正负10000
|