C++-এ দ্বিতীয় অ্যারে রি-অ্যারেঞ্জ করে লেক্সিকোগ্রাফিক্যালি স্মলেস্ট সিকোয়েন্স বের করা

সমস্যা

দুই অ্যারে A ও B (সাইজ n) দেওয়া। B-কে রি-অ্যারেঞ্জ করুন যাতে সিকোয়েন্স C[i] = (A[i] + B[i]) % n লেক্সিকোগ্রাফিক্যালি স্মলেস্ট হয়।

অ্যালগরিদম: গ্রিডি + অর্ডার্ড সেট + ফ্রিকোয়েন্সি ম্যাপ

1. B-এর এলিমেন্টগুলো ফ্রিকোয়েন্সি ম্যাপ my_map ও সেট my_set-এ রাখুন।
2. প্রতিটি i (০ থেকে n-1) এর জন্য:
   • যদি A[i] == 0: সেট থেকে সবচেয়ে ছোট এলিমেন্ট নিন।
   • অন্যথায়: x = n - A[i]। সেট থেকে x বা তার চেয়ে বড় এলিমেন্ট খুঁজুন (lower_bound)। না পেলে সবচেয়ে ছোট এলিমেন্ট নিন।
   • বাছাইকৃত মান val দিয়ে (A[i] + val) % n আউটপুটে যোগ করুন।
   • my_map[val]--; যদি ০ হয় তবে সেট থেকে মুছুন।

C++ কোড

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

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 x : b) { my_map[x]++; my_set.insert(x); }
    vector<int> sequence;
    for (int i=0; i

আউটপুট
0 0 1 2