Hướng dẫn cho MEX
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
\(\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
Bình luận
N7hoatt Em vẫn chưa thực sự hiểu được tại sao lại có cách giải như vậy ???
thì nhận xét và đánh giá thì nó ra như vậy, còn về cách suy nghĩ ra nó thì mình chịu, mình chỉ nhìn thấy dãy có tính chất như vậy và xem thử làm cách nào để áp dụng nó để giải bài, mình thấy cách đó đúng nên lấy nó làm ý tưởng triển khai. Đầu tiên đánh giá việc sắp xếp lại dãy ko ảnh hưởng tới kết quả bài toán, tiếp theo mình tìm ra A[i]−i sẽ là lượng Mex tối đa có thể thêm vào từ 1→A[i], rồi mình giải bài dựa trên nó thôi.