Problem

4/6

std::マージ

Theory Click to read/hide

merge - 2 つのソートされた配列をマージする関数。つまり、線形時間で、最初と 2 番目の配列の要素で構成されるソートされた配列を取得します。
これは 5 つの引数を取ります。各配列の 2 つの境界と、宛先 (結果の配列の要素が配置される場所) の左境界です。
詳細については、ドキュメントをご覧ください。

例: // ソース配列はソートする必要があります ベクトル 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] // 要素は繰り返し可能 a = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.resize(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 の場合です。
この配列をマージしてソート ツリーを構築する必要があります。 
これは、葉が配列の要素であるバイナリ ツリーであり、各内部ノードには、このノードのサブツリーにある葉を持つ配列の要素で構成される並べ替えられた配列が含まれます (理解のために例を参照してください)。
ツリー ノードは、最下層 (葉の層) から上に、層内では左から右に番号が付けられます。番号は 1 から始まり、連続しています。シートの番号が 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!