P195SUMA - Số nguyên dương nhỏ nhất

Đọc đề trên PTIT SPOJ

Đề bài

Cho mảng $a$ gồm $n$ phần tử và số nguyên $k$. Tìm số nguyên dương $x$ nhỏ nhất sao cho có đúng $k$ phần tử trong $a$ nhỏ hơn hoặc bằng $x$. Nếu không có số $x$ nào thỏa mãn thì in ra $-1$.

Điều kiện:

• $0 \leq k \leq n$
• $1 \leq n \leq  2\times10^5$
• $0 < a_i \leq 10^9$

Giải: 

Algoritham - đầu tiên sort các phần tử và lấy $x = a[k - 1]$, xong đếm $k_1$ là số lượng số $a_i \leq x$ trong mảng. Nếu $k_1 > k$ thì không tồn tại số nguyên $x$ cần tìm.

Đúng chưa ta? Chú ý những phần in đậm trên đề, thêm điều kiện $k \geq 0$. Đề chỉ bào tìm một số nguyên dương $x$, không nói gì đến chuyện $x$ phải là một phần tử của mảng $a$.

Ví dụ testcase sau:

$5\ 0$

$2\ 2\ 3\ 3\ 4$

Nếu làm theo Algoritham bình thường thì đáp án sẽ là $-1$ - sai lè vì ta vẫn có thể cho $x = 1$ là một số nguyên dương và không có phần tử nào của mảng $\geq x$. Vì vậy, ta phải xét corner case $k = 0$: nếu $a[0] = 1$ thì không có đáp án, còn lại đáp án là $1$. Với $k \neq 0$ thì làm như ban đầu.

Đây là code mẫu

Nhận xét

Bài toán này không hề khó mà chỉ tricky ở cái điều kiện. Tất nhiên là nếu như bạn không bị ngu như mình thì mình nghĩ bạn sẽ solve xong trong 1-2 sub gì đấy thôi :/

Happy coding!