MEX

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong lý thuyết trò chơi hàm \(mex\) đóng vai trò quan trọng. Hàm \(mex\) được định nghĩa như sau:
Cho tập số nguyên dương \(A\). \(mex(A)\) là số nguyên dương nhỏ nhất không có trong tập \(A\). Ví dụ,
với \(A = {2,1,3,5,100}\), \(mex(A) = 4\), với \(A = {2,3,4,5}\), \(mex(A) = 1\).

Alice rất thích thú với vai trò và ứng dụng của hàm \(mex\). Sẵn có trong tay dãy số nguyên dương \(A = (a_1, a_2, . . ., a_n)\), trong đó các số khác nhau từng đôi một, Alice quyết định thực hiện k lần phép
bổ sung \(mex\) vào dãy, mỗi lần đưa thêm vào \(A\) số \(mex\) tìm được và làm tăng số phần tử của dãy
lên 1.

Hãy xác định giá trị của phần tử cuối cùng được bổ sung vào dãy.

Input

  • Dòng đầu tiên chứa 2 số nguyên \(n\) và \(k\) (\(1 \le n \le 10^5, 1 \le k \le 10^9\)),
  • Dòng thứ 2 chứa \(n\) số nguyên khác nhau \(a_1, a_2, . . ., a_n (1 \le a_i \le 10^5, i = 1 ÷ n)\).

Output

  • Đưa ra một số nguyên – giá trị số cuối cùng được bổ sung vào
    dãy.

Example

Test 1

Input 
7 10
1 3 20 2 7 45 5
Output 
15

Bình luận


  • 0
    huyhau6a2    9:51 p.m. 28 Tháng 12, 2021

    cái này chặt nhị phân 2 lần được


    • 0
      phambinminh12345    8:40 a.m. 14 Tháng 11, 2021

      hello

      1 phản hồi

      • 0
        ekhoavvdd    2:03 p.m. 29 Tháng 5, 2021

        sao ở test 1
        giới hạn mảng a với n,k sao lớn hơn đề vậy thầy :))


        • 3
          N7hoatt    11:29 a.m. 9 Tháng 5, 2021 ← đã chỉnh sửa

          \(\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ớ}}}}\)

          C++
          #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;
}

          p/s : có gì khó hiểu thì bạn cứ hỏi mình