Dãy chữ điển nhỏ nhất bằng cách sắp xếp lại mảng thứ hai trong C++

Cho mảng A, B cùng kích thước n. Sắp xếp lại B sao cho dãy C[i] = (A[i] + B[i]) % n nhỏ nhất theo thứ tự từ điển (lexicographically).

Ví dụ

A = {1,2,3,2}, B = {4,3,2,2}

Output: [0, 0, 1, 2]

Thuật toán tham lam + Multiset

• Duyệt i từ 0 đến n-1.
• Với A[i], cần chọn x ∈ B còn lại sao cho (A[i] + x) % n nhỏ nhất.
• Mục tiêu: (A[i] + x) % n = 0 nếu có thể → cần x ≡ (n - A[i]) % n.
• Dùng multiset + lower_bound tìm x ≥ target, nếu không có lấy phần tử nhỏ nhất.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

vector<int> solve(vector<int>& a, vector<int>& b) {
    int n = a.size();
    multiset<int> ms(b.begin(), b.end());
    vector<int> res;
    
    for (int x : a) {
        int need = (n - x) % n;
        auto it = ms.lower_bound(need);
        if (it == ms.end()) it = ms.begin(); // wrap around
        int val = *it;
        res.push_back((x + val) % n);
        ms.erase(it);
    }
    return res;
}

int main() {
    vector<int> a = {1,2,3,2};
    vector<int> b = {4,3,2,2};
    auto res = solve(a, b);
    for (int x : res) cout << x << " ";
    return 0;
}

Kết quả

0 0 1 2

Độ phức tạp: O(n log n) do multiset.