Problem

4/6

标准::合并

Theory Click to read/hide

merge - 合并两个排序数组的函数，即在线性时间内它得到一个排序数组，它由第一个和第二个数组的元素组成。
它有 5 个参数：每个数组的两个边界和目标的左边界（将放置结果数组的元素的位置）。
可以在文档中找到更多详细信息。

例子： // 源数组必须排序 矢量 a = { 1, 3, 5, 7 }; 矢量 b = { 2, 4, 6 }; // 需要目的地足够大 矢量 c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // 元素可以重复 一 = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.调整大小（10）； merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  这个函数在归并排序的上下文中非常有用。

Problem

给定一个大小为 n 的数组 A，其中 n = 2m 对于某个自然 m。
你需要通过合并这个数组来构建一个排序树。 
这是一棵二叉树，其中的叶子是一个数组的元素，每个内部节点包含一个排序数组，该数组由那些叶子在该节点的子树中的数组元素组成（请参见示例以了解）。
树节点从底层（叶层）到顶部编号，在层内从左到右。编号从一开始连续。如果工作表的编号为 i，则它包含值 Ai。
以下是 n = 4 的树编号示例。

     7
    / \
   /  \
  5    6
 / \    /  \
1  2 3   4

输入：
第一行包含数字 n (2 <= n <= 215) - 数组 A 的大小。
下一行包含 n 个整数 Ai (-109 <= A_i <= 109) - 数组元素。

输出：
打印 2*n-1 行 - 第 i 行包含树的第 i 个节点包含的元素。

示例：
  <正文>

解释：

   [-322, 5, 10, 97]
      /           \
     /              \
 [-322, 97]   [5, 10]
  /          \       /    \
[97]  [-322] [5]   [10]
 

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	vector<vector<int>> tree(2 * n - 1);
	for (int i = 0; i < n; i++)
		tree[i] = { arr[i] };

	int child = 0;
	for (int i = n; i < tree.size(); i++) {   
		child += 2;
	}

	for (int i = 0; i < tree.size(); i++) {
		for (int j = 0; j < tree[i].size(); j++)
			cout << tree[i][j] << ' ';
		cout << endl;
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!