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] Lập lịch đĩa SCAN (thang máy)

    Mô phỏng lập lịch đĩa SCAN (thuật toán thang máy / elevator) và tính tổng quãng đường di chuyển đầu đọc.

    Đầu đọc bắt đầu ở start và đi theo hướng tăng (lên phía track lớn) trước. Nó phục vụ mọi yêu cầu ≥ start theo thứ tự tăng dần, đi tới biên trên disk_max (track lớn nhất của đĩa), rồi đảo chiều đi xuống phục vụ các yêu cầu < start theo thứ tự giảm dần.

    Lưu ý: chỉ chạm biên disk_max nếu còn yêu cầu ở phía dưới cần phục vụ sau khi đảo chiều (theo mô tả chuẩn của SCAN: đầu đọc chạm biên rồi mới quay lại).

    Thuật toán:

    1. Chia yêu cầu thành nhóm right (≥ start, sắp tăng) và left (< start, sắp tăng).
    2. Phục vụ right tăng dần (cộng khoảng cách, dời đầu đọc).
    3. Nếu còn left: đi tới disk_max (cộng |disk_max - cur|), rồi phục vụ left giảm dần.
    4. In tổng quãng đường.

    Ví dụ: start=50, disk_max=199, yêu cầu 82 170 43 140. right=[82,140,170], left=[43]. Đi 50→82→140→170 (=120), →199 (=29), →43 (=156). Tổng = 120+29+156 = 305.

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

      Dòng 1: n, start, disk_max. Dòng 2: n số — các yêu cầu.

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

      1 ≤ n ≤ 100000; 0 ≤ yêu cầu ≤ disk_max ≤ 1000000; 0 ≤ start ≤ disk_max.

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

      Một số nguyên: tổng quãng đường di chuyển.

    Ví dụ:

    Đầu vào:

    4 50 199
82 170 43 140

    Đầu ra:

    305

    Giải thích:

    right(≥50)=[82,140,170], left(<50)=[43]. Đi lên: 50→82(32)→140(58)→170(30)=120, cur=170. Còn left → tới biên 199 (|199-170|=29), cur=199. Xuống: 199→43 (156). Tổng = 120+29+156 = 305.

    Đang tải editor...