मान लीजिए हमारे पास n संख्याओं के दो ऐरे A और B हैं, हमें B के तत्वों को स्वयं में इस तरह पुनर्व्यवस्थित करना है कि पुनर्व्यवस्थित करने के बाद (A[i] + B[i]) % n से बना अनुक्रम लेक्सिकोग्राफिकली सबसे छोटा हो। अंत में हम लेक्सिकोग्राफिकली सबसे छोटा संभव अनुक्रम लौटाएंगे।
उदाहरण के लिए, यदि इनपुट A = {1, 2, 3, 2}, B = {4, 3, 2, 2} है, तो आउटपुट [0, 0, 1, 2] होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- n := a का आकार
- my_map नामक एक मैप परिभाषित करें
- my_set नामक एक सेट परिभाषित करें
- i := 0 से n-1 तक लूप करें:
- my_map[b[i]] बढ़ाएं
- b[i] को my_set में डालें
- सीक्वेंस नामक एक ऐरे परिभाषित करें
- i := 0 से n-1 तक लूप करें:
- यदि a[i] 0 के बराबर है:
- it := my_set के तत्व जो 0 से छोटे नहीं हैं, शुरू में पहले तत्व पर इंगित करते हैं
- वैल्यू := it
- वैल्यू % n को सीक्वेंस के अंत में डालें
- my_map[वैल्यू] घटाएं
- यदि my_map[वैल्यू] शून्य है, तो my_set से वैल्यू हटाएं
- अन्यथा:
- x := n - a[i]
- it := my_set के तत्व जो x से छोटे नहीं हैं, शुरू में पहले तत्व पर इंगित करते हैं
- यदि it my_set में नहीं है, तो it := my_set के तत्व जो 0 से छोटे नहीं हैं
- वैल्यू := it
- (a[i] + वैल्यू) % n को सीक्वेंस के अंत में डालें
- my_map[वैल्यू] घटाएं
- यदि my_map[वैल्यू] शून्य है, तो my_set से वैल्यू हटाएं
- यदि a[i] 0 के बराबर है:
- सीक्वेंस लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v) { cout << "["; for (int i = 0; i < v.size(); i++) { cout << v[i] << ", "; } cout << "]" << endl; } vector<int> solve(vector<int>&a, vector<int> &b) { int n = a.size(); unordered_map<int, int> my_map; set<int> my_set; for (int i = 0; i < n; i++) { my_map[b[i]]++; my_set.insert(b[i]); } vector<int> sequence; for (int i = 0; i < n; i++) { if (a[i] == 0) { auto it = my_set.lower_bound(0); int value = *it; sequence.push_back(value % n); my_map[value]--; if (!my_map[value]) my_set.erase(value); } else { int x = n - a[i]; auto it = my_set.lower_bound(x); if (it == my_set.end()) it = my_set.lower_bound(0); int value = *it; sequence.push_back((a[i] + value) % n); my_map[value]--; if (!my_map[value]) my_set.erase(value); } } return sequence; } int main() { vector<int> a = {1, 2, 3, 2}; vector<int> b = {4, 3, 2, 2}; vector<int> res = solve(a, b); print_vector(res); } इनपुट
{1, 2, 3, 2}, {4, 3, 2, 2} आउटपुट
[0, 0, 1, 2, ]