Problem

4/6

std::ادغام

Theory Click to read/hide

merge - تابعی که دو آرایه مرتب شده را ادغام می کند، یعنی در زمان خطی یک آرایه مرتب شده دریافت می کند که از عناصر آرایه اول و دوم تشکیل شده است.
این 5 آرگومان نیاز دارد: دو کران برای هر آرایه و کران سمت چپ مقصد (جایی که عناصر آرایه حاصل قرار می گیرند).
جزئیات بیشتر را می‌توانید در اسناد پیدا کنید.

مثال ها: // آرایه های منبع باید مرتب شوند بردار a = { 1, 3, 5, 7 }; بردار b = { 2, 4, 6 }; // باید مقصد به اندازه کافی بزرگ باشد vector 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

یک آرایه A به اندازه n داده می شود، جایی که 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-ام درخت است.

مثال:
  <بدن>
ورودی خروجی
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97


توضیح:

   [-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++
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!