หา Lexicographically Smallest Sequence จากการจัดเรียง Array B ใหม่ใน C++

โจทย์: กำหนด array A, B ขนาด n จัดเรียง B ใหม่ ให้ sequence (A[i] + B[i]) % n มี lexicographically smallest คืน sequence นั้น

ตัวอย่าง: A={1,2,3,2}, B={4,3,2,2} → output [0,0,1,2]

อัลกอริธึม: Greedy + Ordered Multiset

1. เก็บ frequency ของ B ใน map และค่า unique ใน set (ordered)
2. วน i = 0..n-1:
   • ถ้า A[i] == 0: เลือกค่าน้อยที่สุดใน set (≥ 0)
   • ถ้า A[i] > 0: ต้องการ (A[i] + x) % n น้อยที่สุด → ต้องการ x ≥ n - A[i] (lower_bound) ถ้าไม่มี ให้วนรอบเลือกค่าน้อยที่สุด (lower_bound 0)
   • อัปเดต frequency ลบออกจาก set ถ้าหมด

ตัวอย่างโค้ด C++

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

Complexity

• Time: O(N log N) จาก set operations
• Space: O(N)