Problem

4/6

std::merge

Theory Click to read/hide

hợp nhất - một hàm hợp nhất hai mảng đã sắp xếp, cụ thể là trong thời gian tuyến tính, nó nhận được một mảng đã sắp xếp, bao gồm các phần tử của mảng thứ nhất và thứ hai.
Nó nhận 5 đối số: hai giới hạn cho mỗi mảng và giới hạn bên trái của đích (nơi các phần tử của mảng kết quả sẽ được đặt).
Bạn có thể tìm thêm chi tiết trong tài liệu.

Ví dụ: // mảng nguồn phải được sắp xếp vectơ a = { 1, 3, 5, 7 }; vectơ b = {2, 4, 6}; // cần đích đủ lớn vecto c(7); hợp nhất (a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // các phần tử có thể được lặp lại a = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.resize(10); hợp nhất (a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Hàm này rất hữu ích trong bối cảnh sắp xếp hợp nhất.

Problem

Cho một mảng A có kích thước n, trong đó n = 2m với một số m tự nhiên.
Bạn cần tạo cây sắp xếp bằng cách hợp nhất mảng này. 
Đây là cây nhị phân trong đó các lá là phần tử của một mảng và mỗi nút bên trong chứa một mảng đã sắp xếp bao gồm các phần tử của mảng có các lá nằm trong cây con của nút này (xem ví dụ để hiểu).
Các nút của cây được đánh số từ lớp dưới cùng (lớp lá) lên trên, bên trong lớp từ trái sang phải. Việc đánh số bắt đầu từ một và liên tục. Nếu trang tính có số i, thì trang tính đó chứa giá trị Ai.
Dưới đây là một ví dụ về đánh số cây cho n = 4.

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

Đầu vào:
Dòng đầu tiên chứa số n (2 <= n <= 215) - kích thước của mảng A.
Dòng tiếp theo chứa n số nguyên Ai (-109 <= A_i <= 109) - phần tử mảng.

Đầu ra:
In 2*n-1 dòng - dòng thứ i chứa các phần tử có trong nút thứ i của cây.

Ví dụ:
 

Giải thích:

   [-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++
Đầu vào Đầu ra
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!