Tóm đề

Chèn số ~K~ vào số ~X~ sao cho số mới là lớn nhất

Với ~N \le 10^4~

Ta thử chèn ~K~ vào mọi vị trí của ~X~ và so sánh.

Độ phức tạp: ~ \mathcal{O}(n^2).~

Code tham khảo của lds

void lds_go_goooo()
{
    string ans=str;
    FOR(i,0,str.size())
    {
        string tmp=str;
        tmp.insert(i,k);
        ans=max(ans,tmp);
    }
    cout<<ans;
}

Với ~N \le 2 \cdot 10^6~

Thử với nhiều trường hợp, ta nhận thấy rằng chỉ cần chèn ~K~ vào vị trí ~i~ ~(0 \le i \le N)~ của ~X~ mà giá trị nhỏ hơn ~K~ thì sẽ cho ra số lớn nhất.

Độ phức tạp: ~ \mathcal{O}(n).~

Code tham khảo của lds

void lds_go_goooo()
{
    FOR(i,0,n)
        if(str[i]<k[0])
       {
           str.insert(i,k);
           break;
       }
      cout<<str;
}