Problem

4/6

एसटीडी :: विलय

Theory Click to read/hide

मर्ज - एक फ़ंक्शन जो दो क्रमबद्ध सरणियों को मर्ज करता है, अर्थात्, रैखिक समय में यह एक क्रमबद्ध सरणी प्राप्त करता है, जिसमें पहली और दूसरी सरणी के तत्व होते हैं।
इसमें 5 तर्क होते हैं: प्रत्येक सरणी के लिए दो सीमाएँ और गंतव्य की बाईं सीमा (जहाँ परिणामी सरणी के तत्व रखे जाएंगे)।
अधिक विवरण दस्तावेज़ीकरण में पाया जा सकता है।

उदाहरण: // स्रोत सरणियों को क्रमबद्ध किया जाना चाहिए वेक्टर ए = {1, 3, 5, 7}; वेक्टर <इंट> बी = {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}; सी. आकार बदलें (10); विलय (a.begin (), a.end (), b.begin (), b.end (), c.begin ()); // सी = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  मर्ज सॉर्ट के संदर्भ में यह फ़ंक्शन बहुत उपयोगी है।

Problem

आकार n की एक सरणी A दी गई है, जहाँ 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-वें नोड में निहित तत्व शामिल हैं।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 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!