C++で2番目の配列の要素を再配置することによって形成できる辞書式順序で最小のシーケンスを見つけます

n個の数を持つ2つの配列AとBがあるとすると、（A [i] + B [によって形成されるシーケンスになるように、Bの要素自体を再配置する必要があります。 i]）再配置後の％nは、辞書式順序で最小です。最後に、辞書式順序で可能な限り最小のシーケンスを返します。

したがって、入力がA ={1、2、3、2}、B ={4、3、2、2}の場合、出力は[0、0、1、2]

これを解決するには、次の手順に従います-

• n：=a

  のサイズ

• 1つのマップを定義するmy_map

• 1つのセットを定義するmy_set

• 初期化i：=0の場合、i

  • （my_map [b [i]]を1増やします）

  • b[i]をmy_setに挿入します

• 配列シーケンスを定義する

• 初期化i：=0の場合、i

  • a [i]が0と同じ場合、-

    • it：=0以上のmy_setの要素で、最初は最初の要素を指します

    • 値：=it

    • シーケンスの最後に値modnを挿入します

    • （my_map [value]を1減らします）

    • my_map [value]がゼロの場合、-

      • my_setから値を削除

• それ以外の場合

  • x：=n-a [i]

  • it：=x以上のmy_setの要素は、最初は最初の要素を指します

  • my_setにない場合は、-

    • it：=0以上のmy_setの要素で、最初は最初の要素を指します

  • 値：=it

  • シーケンスの最後に（a [i] + value）modnを挿入します

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