\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• nhận xét : Nếu sắp xếp lại mảng \(A\) thì \(A[i] - i\) sẽ là lượng \(Mex\) tối đa có thể thêm vào từ \(1 → A[i]\)

• để tìm được giá trị cuối cùng cần được bổ sung:

  tìm \(i\) sao cho \(A[i] - i < k\) và \(i\) lớn nhất, giá trị cuối cùng sẽ bằng \(k + i\)

\(\color{goldenrod}{\text{Tiếp cận}}\)

• đầu tiên ta sắp xếp lại mảng
• ta chạy kiểm tra từ \(0 → n - 1\), nếu \(A[i + 1] - (i + 1) >= k\) thì dừng và in ra \(k + i\)

\(\color{green}{\text{Code tham khảo }}\): Sorting

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(nlog(n) + n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

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

ll a[100005];
ll n, k;
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    int i;
    for(i = 0; i < n; ++i){
        if(a[i + 1] - i - 1 < k) continue;
        else break;
    }
    cout << i + k;
}