Problem

4/6

الأمراض المنقولة جنسيا :: دمج

Theory Click to read/hide

دمج - دالة تدمج مصفوفتين مرتبة ، أي في الوقت الخطي تحصل على مصفوفة مرتبة ، تتكون من عناصر المصفوفة الأولى والثانية.
يأخذ 5 وسائط: حدين لكل مصفوفة والحد الأيسر للوجهة (حيث سيتم وضع عناصر المصفوفة الناتجة).
يمكن العثور على مزيد من التفاصيل في الوثائق .

أمثلة: // يجب فرز مصفوفات المصدر المتجه a = {1، 3، 5، 7} ؛ المتجه b = {2، 4، 6} ؛ // بحاجة إلى أن تكون الوجهة كبيرة بما يكفي ناقلات ج (7) ؛ دمج (a.begin () ، a.end () ، b.begin () ، b.end () ، c.begin ()) ؛ // ج = [1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7] // يمكن تكرار العناصر أ = {1، 2، 4، 4} ؛ ب = {2 ، 3 ، 3 ، 3 ، 4 ، 4} ؛ c.resize (10) ؛ دمج (a.begin () ، a.end () ، b.begin () ، b.end () ، c.begin ()) ؛ // ج = [1 ، 2 ، 2 ، 3 ، 3 ، 3 ، 4 ، 4 ، 4 ، 4] على & nbsp ؛ هذه الوظيفة مفيدة جدًا في سياق فرز الدمج.

Problem

بالنظر إلى مصفوفة A بالحجم n ، حيث n = 2 m لبعض المتر الطبيعي.
تحتاج إلى بناء شجرة فرز عن طريق دمج هذه المصفوفة. & nbsp؛
هذه شجرة ثنائية حيث الأوراق هي عناصر المصفوفة ، وتحتوي كل عقدة داخلية على مصفوفة مرتبة تتكون من عناصر المصفوفة التي توجد أوراقها في شبكة فرعية من هذه العقدة (انظر أمثلة للفهم).
يتم ترقيم عقد الشجرة من الطبقة السفلية (طبقة الورقة) إلى الأعلى ، داخل الطبقة من اليسار إلى اليمين. يبدأ الترقيم من واحد ومستمر. إذا كانت الورقة تحتوي على الرقم i ، فإنها تحتوي على القيمة A i .
يوجد أدناه مثال على ترقيم الشجرة لـ n = 4.

نبسب ؛ نبسب ؛ نبسب؛ 7
نبسب ؛ نبسب ؛ / \
نبسب ؛ نبسب ؛ / نبسب ؛ \
نبسب ؛ 5 نبسب ؛ نبسب ؛ 6
على & nbsp ؛ / \ & nbsp ؛ نبسب ؛ / نبسب ؛ \
1 نبسب ؛ 2 3 نبسب ؛ 4

الإدخال:
يحتوي السطر الأول على الرقم n (2 & lt؛ = n & lt؛ = 2 15 ) - حجم المصفوفة أ.
يحتوي السطر التالي على n أعداد صحيحة A i (-10 9 & lt؛ = A_i & lt؛ = 10 9 ) - عناصر المصفوفة.

الإخراج:
اطبع سطور 2 * n-1 - يحتوي السطر الأول على العناصر الموجودة في العقدة الأولى من الشجرة.

مثال:
نبسب ؛ <الجسم>
إدخال الإخراج
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]
نبسب ؛ / نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ نبسب ؛ \ & nbsp ؛ نبسب ؛ نبسب ؛ نبسب ؛ / نبسب ؛ نبسب ؛ \
[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!