Problem

4/6

std::birleştirme

Theory Click to read/hide

birleştirme - iki sıralanmış diziyi birleştiren bir işlev, yani lineer zamanda birinci ve ikinci dizinin öğelerinden oluşan sıralanmış bir dizi alır.
5 bağımsız değişken alır: her dizi için iki sınır ve hedefin sol sınırı (sonuçta elde edilen dizinin öğelerinin yerleştirileceği yer).
Daha fazla ayrıntıyı belgelerde bulabilirsiniz.

Örnekler: // kaynak dizileri sıralanmalıdır vektör a = { 1, 3, 5, 7 }; vektör b = { 2, 4, 6 }; // hedefin yeterince büyük olması gerekiyor vektör c(7); birleştirme(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // elemanlar tekrarlanabilir bir = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.boyutlandır(10); birleştirme(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Bu işlev, birleştirme sıralaması bağlamında çok kullanışlıdır.

Problem

Bazı doğal m'ler için n = 2m olmak üzere, n boyutunda bir A dizisi verilsin.
Bu diziyi birleştirerek bir sıralama ağacı oluşturmanız gerekiyor. 
Bu, yaprakların bir dizinin öğeleri olduğu ikili bir ağaçtır ve her dahili düğüm, yaprakları bu düğümün alt ağacında bulunan dizi öğelerinden oluşan sıralanmış bir dizi içerir (anlamak için örneklere bakın).
Ağaç düğümleri, alt katmandan (yaprak katman) üste, katman içinde soldan sağa doğru numaralandırılmıştır. Numaralandırma birden başlar ve süreklidir. Sayfa i sayısına sahipse Ai değerini içerir.
Aşağıda n = 4 için ağaç numaralandırma örneği verilmiştir.

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

Giriş:
İlk satır n sayısını içerir (2 <= n <= 215) - A dizisinin boyutu.
Sonraki satır n tam sayı Ai (-109 <= A_i <= 109) içerir - dizi öğeleri.

Çıktı:
2*n-1 satır yazdır - i. satır, ağacın i. düğümünde yer alan öğeleri içerir.

Örnek:
 

Açıklama:

   [-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++
Giriş Çıktı
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!