Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Hệ điều hành] Working set — kích thước tập làm việc

    Working Set — kích thước tập làm việc theo thời gian

    Working set W(t, τ) là tập các trang khác nhau được tham chiếu trong cửa sổ τ lần truy cập gần nhất tính đến thời điểm t (bao gồm cả tham chiếu tại t).

    Thuật toán

    • Cho cửa sổ τ và chuỗi tham chiếu refs[0..m-1].
    • Với mỗi t = 0…m-1: lấy đoạn refs[max(0, t-τ+1) .. t], đếm số trang phân biệt trong đoạn đó → kích thước working set tại t.

    In dãy kích thước working set tại mọi thời điểm, rồi in kích thước lớn nhất.

    Ví dụ

    τ=3, chuỗi 1 2 1 3. t=0: {1}→1. t=1: {1,2}→2. t=2: cửa sổ [0..2] {1,2,1}→2. t=3: cửa sổ [1..3] {2,1,3}→3. Dãy 1 2 2 3, max=3.

    • Định dạng đầu vào:

      Dòng 1: τ — kích thước cửa sổ. Dòng 2: m. Dòng 3: m số hiệu trang.

    • Ràng buộc đầu vào:

      1 ≤ τ ≤ 1000; 1 ≤ m ≤ 10^4; 0 ≤ số_trang ≤ 10^5.

    • Định dạng đầu ra:

      Dòng 1: m số — kích thước working set tại mỗi thời điểm. Dòng 2: kích thước lớn nhất.

    Ví dụ:

    Đầu vào:

    3
4
1 2 1 3

    Đầu ra:

    1 2 2 3
3

    Giải thích:

    τ=3. t0:{1}=1; t1:{1,2}=2; t2: cửa sổ [0..2]={1,2}=2; t3: cửa sổ [1..3]={2,1,3}=3. Dãy 1 2 2 3, max=3.

    Đang tải editor...