Problem

4/6

표준::병합

Theory Click to read/hide

병합 - 두 개의 정렬된 배열을 병합하는 기능, 즉 선형 시간에 첫 번째 및 두 번째 배열의 요소로 구성된 정렬된 배열을 얻습니다.
5개의 인수를 취합니다: 각 배열에 대한 두 개의 경계와 대상의 왼쪽 경계(결과 배열의 요소가 배치될 위치).
자세한 내용은 문서에서 확인할 수 있습니다.

예: // 소스 배열을 정렬해야 합니다. 벡터 a = { 1, 3, 5, 7 }; 벡터 b = { 2, 4, 6 }; // 대상이 충분히 커야 함 vectorc(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가 주어졌는데, 여기서 일부 자연 m의 경우 n = 2m입니다.
이 배열을 병합하여 정렬 트리를 구축해야 합니다. 
이것은 잎이 배열의 요소인 이진 트리이며 각 내부 노드에는 잎이 이 노드의 하위 트리에 있는 배열의 요소로 구성된 정렬된 배열이 포함됩니다(이해를 위한 예 참조).
트리 노드는 아래쪽 레이어(리프 레이어)에서 위쪽으로, 레이어 내부에서는 왼쪽에서 오른쪽으로 번호가 매겨집니다. 번호 매기기는 1부터 시작하여 연속적입니다. 시트에 숫자 i가 있으면 값 Ai가 포함됩니다.
다음은 n = 4에 대한 트리 번호 매기기의 예입니다.

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

입력:
첫 번째 줄에는 배열 A의 크기인 숫자 n(2 <= n <= 215)이 포함됩니다.
다음 줄에는 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!