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).
★ Code: https://ideone.com/0ADeTB

Comments

Popular posts from this blog

Codeforces - 1433D - Districts Connection

Codeforces - 1462E2 - Close Tuples (hard version)

Kadane's algorithm - Finding maximum rectangular submatrix