Hướng dẫn cho Dãy con min max
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{Hint 1 <Brute-forces>}}\)
Tìm \(max\), \(min\) của dãy \(a\)
Tạo ra mảng \(amx\) chứa các vị trí \(p\) mà \(a_p = max\)
Tạo ra mảng \(amn\) chứa các vị trí \(p\) mà \(a_p = min\)
Duyệt qua 2 mảng, tìm \(min{ |amx_i - amn_j| + 1 }\)
\(\color{orange}{\text{Hint 2 <Binary-Search>}}\)
Nhận xét rằng nếu ta nhận lần lượt các giá trị \(a[p]\) cho 2 mảng \(amn\) và \(amx\) thì nó đã được sắp xếp
Áp dụng điều này, duyệt mỗi \(x \in amx[]\) và tìm \(min{ |x - amn_i| }\)
Lưu ý xét cả 2 số \(amn_i \leq x\) và \(amn_{i + 1} \geq x\)
\(\color{orange}{\text{Hint 3 <Two-pointers>}}\)
Tương tự như trên, nhưng ta nhận thấy nếu 2 mảng \(amn\) và \(amx\) cùng sort theo độ ưu tiên như nhau (cùng tăng hoặc cùng giảm) thì ta có thể tăng dần vị trí con trỏ của một bên tới khi nó đạt giá trị phù hợp nhất và cập nhật kết quả
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Mình viết editorial đôi lúc không tránh khỏi sai sót nên nếu bạn nào thấy gì sai thì nhắc mình nhé UwU
Nếu bạn nào thấy khó hiểu chỗ nào hoặc muốn xem code tham khảo thì gọi mình để mình Expand Editorial ra nhé UwU