ค้นหาลำดับที่เล็กที่สุดเกี่ยวกับคำศัพท์ซึ่งสามารถเกิดขึ้นได้โดยการจัดเรียงองค์ประกอบของอาร์เรย์ที่สองใน C ++ ใหม่

สมมติว่าเรามีอาร์เรย์ A และ B สองอาร์เรย์ที่มีตัวเลข n อยู่ เราต้องจัดเรียงองค์ประกอบของ 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)

  • แทรก b[i] ลงใน my_set

• กำหนดลำดับอาร์เรย์

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า a[i] เท่ากับ 0 แล้ว −

    • it :=องค์ประกอบของ my_set ซึ่งไม่เล็กกว่า 0 เริ่มแรกให้ชี้ไปที่องค์ประกอบแรก

    • ค่า :=มัน

    • แทรกค่า mod n ที่ส่วนท้ายของลำดับ

    • (ลด my_map[value] ลง 1)

    • ถ้า my_map[value] เป็นศูนย์ ดังนั้น −

      • ลบค่าจาก my_set

• มิฉะนั้น

  • x :=n - a[i]

  • it :=องค์ประกอบของ my_set ซึ่งไม่เล็กกว่า x เริ่มแรกให้ชี้ไปที่องค์ประกอบแรก

  • ถ้ามันไม่ได้อยู่ใน my_set แล้ว −

    • it :=องค์ประกอบของ my_set ซึ่งไม่เล็กกว่า 0 เริ่มแรกให้ชี้ไปที่องค์ประกอบแรก

  • ค่า :=มัน

  • แทรก (a[i] + ค่า) 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, ]