আভিধানিকভাবে ক্ষুদ্রতম ক্রম খুঁজুন যা 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 :=a

  এর আকার

• একটি মানচিত্র my_map

  সংজ্ঞায়িত করুন

• একটি সেট my_set

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • (my_map[b[i]] 1 দ্বারা বাড়ান)

  • my_set

    -এ b[i] ঢোকান

• একটি অ্যারের ক্রম সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি a[i] 0 এর সমান হয়, তাহলে −

    • এটা :=my_set এর উপাদান যা 0 এর থেকে ছোট নয়, প্রাথমিকভাবে প্রথম উপাদানের দিকে নির্দেশ করে

    • মান :=এটা

    • অনুক্রমের শেষে মান mod n সন্নিবেশ করুন

    • (my_map[মান] 1 দ্বারা কমিয়ে দিন)

    • যদি my_map[মান] শূন্য হয়, তাহলে −

      • my_set

        থেকে মান মুছে দিন

• অন্যথায়

  • x :=n - a[i]

  • এটা :=my_set-এর উপাদান যা x-এর চেয়ে ছোট নয়, প্রাথমিকভাবে প্রথম উপাদানের দিকে নির্দেশ করে

  • যদি এটি আমার_সেটে না থাকে, তাহলে −

    • এটা :=my_set এর উপাদান যা 0 এর থেকে ছোট নয়, প্রাথমিকভাবে প্রথম উপাদানের দিকে নির্দেশ করে

  • মান :=এটা

  • অনুক্রমের শেষে সন্নিবেশ (a[i] + মান) mod n

  • (my_map[মান] 1 দ্বারা কমিয়ে দিন)

  • যদি my_map[মান] শূন্য হয়, তাহলে −

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