लेक्सिकोग्राफिक रूप से सबसे छोटा अनुक्रम खोजें जो C++ . में दूसरी सरणी के तत्वों को फिर से व्यवस्थित करके बनाया जा सकता है

मान लीजिए कि हमारे पास n संख्याओं के साथ A और B दो सरणियाँ हैं, हमें B के तत्वों को इस तरह से पुनर्व्यवस्थित करना है कि (A[i] + B[ द्वारा गठित अनुक्रम i]) % n को पुनर्व्यवस्थित करने के बाद यह शब्दावली की दृष्टि से सबसे छोटा है। अंत में हम शब्दावली की दृष्टि से सबसे छोटा संभव अनुक्रम लौटाएंगे।

इसलिए, यदि इनपुट A ={1, 2, 3, 2}, B ={4, 3, 2, 2} जैसा है, तो आउटपुट [0, 0, 1, 2]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=आकार का

• एक मानचित्र my_map परिभाषित करें

• एक सेट my_set परिभाषित करें

• इनिशियलाइज़ i:=0 के लिए, जब i

  • (my_map[b[i]] को 1 से बढ़ाएं)

  • my_set में b[i] डालें

• एक सरणी अनुक्रम परिभाषित करें

• इनिशियलाइज़ i:=0 के लिए, जब i

  • अगर a[i] 0 के समान है, तो -

    • it :=my_set के तत्व जो 0 से छोटे नहीं हैं, प्रारंभ में पहले तत्व की ओर इशारा करते हैं

    • मान :=यह

    • अनुक्रम के अंत में मान mod n डालें

    • (my_map[value] को 1 से घटाएं)

    • अगर my_map[value] शून्य है, तो -

      • my_set से मान हटाएं

• अन्यथा

  • एक्स:=एन - एक [i]

  • it :=my_set के तत्व जो x से छोटे नहीं हैं, प्रारंभ में पहले तत्व की ओर इशारा करते हैं

  • अगर यह my_set में नहीं है, तो -

    • it :=my_set के तत्व जो 0 से छोटे नहीं हैं, प्रारंभ में पहले तत्व की ओर इशारा करते हैं

  • मान :=यह

  • अनुक्रम के अंत में (a[i] + value) mod n डालें

  • (my_map[value] को 1 से घटाएं)

  • अगर my_map[value] शून्य है, तो -

    • my_set से मान हटाएं

• वापसी क्रम

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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, ]