PTA | 堆中的路径

目录

题目：

输入格式:

输出格式:

输入样例:

输出样例:

代码：

无注释版：

有注释版： 

---

题目：

将一系列给定数字插入一个初始为空的最小堆 h。随后对任意给定的下标 i，打印从第 i 个结点到根结点的路径。

输入格式:

每组测试第 1 行包含 2 个正整数 n 和 m (≤103)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间 [−104,104] 内的 n 个要被插入一个初始为空的小顶堆的整数。最后一行给出 m 个下标。

输出格式:

对输入中给出的每个下标 i，在一行中输出从第 i 个结点到根结点的路径上的数据。数字间以 1 个空格分隔，行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

代码长度限制16 KB，时间限制400 ms，内存限制64 MB，栈限制8192 KB

代码：

无注释版：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int len=0; 
int heap[100010];
void insert(int x){int i=0;for(i=++len;heap[i/2]>x;i/=2){heap[i]=heap[i/2];}heap[i]=x;
}
signed main(){int n,m;cin>>n>>m;heap[0]=INT_MIN;for(int i=0;i<n;i++){int x;cin>>x;insert(x);}for(int i=0;i<m;i++){int j;cin>>j;cout<<heap[j];while(j>1){j/=2;cout<<" "<<heap[j];}cout<<"\n";}
}

有注释版： 

#include<bits/stdc++.h>
using namespace std;#define int long long // 将 int 定义为 long long，以避免可能的整数溢出
int len = 0; // 记录堆中元素的数量
int heap[100010]; // 用数组 heap 存储最小堆，堆的索引从 1 开始，heap[0] 用于存储无意义的最小值（方便操作）// 插入操作，将元素 x 插入到堆中
void insert(int x) {int i = 0;// 从堆的末尾插入元素，向上调整堆，使堆保持最小堆性质for (i = ++len; heap[i / 2] > x; i /= 2) {heap[i] = heap[i / 2]; // 如果父节点大于当前节点，则将父节点移到当前位置}heap[i] = x; // 将元素 x 插入到正确的位置
}signed main() {int n, m;cin >> n >> m; // 输入 n (堆元素个数) 和 m (需要查询的路径个数)heap[0] = INT_MIN; // 将 heap[0] 初始化为一个不可能出现在堆中的最小值// 输入 n 个数字并插入到堆中for (int i = 0; i < n; i++) {int x;cin >> x; // 输入要插入堆的数字insert(x); // 调用 insert 函数将数字插入到堆中}// 对于每个查询，输出从给定下标到根节点的路径for (int i = 0; i < m; i++) {int j;cin >> j; // 输入查询的下标 jcout << heap[j]; // 输出从下标 j 开始的节点值// 向上遍历父节点，输出从该节点到根节点的路径while (j > 1) {j /= 2; // 向上移动到父节点，父节点的索引为 j / 2cout << " " << heap[j]; // 输出父节点的值}cout << "\n"; // 输出换行}
}