SPOJ - MINK
★ Link: https://codeforces.com/group/FLVn1Sc504/contest/274506/problem/M
★ Difficulty: ezpz
★ Tags: deque
★ Kiến thức: https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
★ Tóm tắt:
Cho dãy a[] gồm n phần tử và số k. Với mỗi vị trí i từ 1 đến n - k + 1, hãy tìm min(a[i], ..., a[i+k-1]).
★ Ý tưởng: sử dụng deque tịnh tiến và CTDL deque.
Đầu tiên ta vẫn tìm vị trí xa nhất về bên phải đối với phần tử i (gọi là r[i]) sao cho a[i] = min(a[i], ...a[r[i]]).
Sau đó vừa duyệt i vừa dùng cấu trúc dữ liệu deque (tương tự vector nhưng có khả năng bỏ phần từ vào trước (front) hoặc sau (back) đều được) để bỏ phần tử chứ i vào phía trước deque. Phần tử ở cuối deque (gọi là j) sẽ là đáp án của vị trí i nếu thoả cả 3 điều kiện sau:
- a[j]<=a[i] (a[j] vẫn là min trong đoạn chứ [j...i].
- r[j]>=i (vì phần tử xa nhất về bên phải của j sao cho a[j] = min(a[j],...,a[r[j]]) vẫn chứa được i, khi đó phần tử i vẫn nằm trong đoạn từ [j...r[j]]).
- j>=i-k+1 (để thoả điều kiện k phần tử liên tiếp).
Comments
Post a Comment