A30286. 堆中的路径
填空题
困难
知识点
题目描述
堆中的路径
题目描述
将一系列给定数字插入一个初始为空的小顶堆`H[]`。随后对任意给定的下标`i`，打印从`H[i]`到根结点的路径。
时间限制： 1000 内存限制： 262144
输入
每组测试第 1 行包含 2 个正整数 N 和 M(≤ 1000)，分别是插入元素的个数、 以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的 N 个要被插入一个初始为空的小顶堆的整数。最后一行给出 M 个下标。
输出
对输入中给出的每个下标`i`，在一行中输出从`H[i]`到根结点的路径上的数据。数字间以 1 个空格分隔，行末不得有多余空格。
样例输入
5 3
46 23 26 24 10
5 4 3
样例输出
24 23 10
46 23 10
26 10
参考答案
#include<stdio.h>
void headAdjust(int *num,int len){
//调整堆，每次插入一个值都对堆自下向上进行一个调整。
int k=len;
num[0]=num[k];
for(int i=len/2;num[i]>num[0];i/=2){
num[k]=num[i];
k=i;
}
num[k]=num[0];
}
int main()
{
int num[1005];
int len=0,n,m,inNum;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++){
scanf("%d",&inNum);
num[++len]=inNum;
headAdjust(num,len);
}
for(int i=1;i<=m;i++){
scanf("%d",&inNum);
while(inNum>=1){
if(inNum==1)
printf("%d",num[inNum]);
else
printf("%d ",num[inNum]);
inNum/=2;
}
if(i!=m)//输出注意格式
printf("\n");
}
}
}
上一题
下一题