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 C-SCAN

    Mô phỏng lập lịch đĩa C-SCAN (Circular SCAN) và tính tổng quãng đường di chuyển đầu đọc.

    C-SCAN: đầu đọc đi theo hướng tăng, phục vụ mọi yêu cầu ≥ start tăng dần, tới biên trên disk_max, rồi nhảy thẳng về biên dưới 0 (quãng đường này được tính = disk_max), sau đó tiếp tục đi lên phục vụ các yêu cầu < start theo thứ tự tăng dần.

    Thuật toán:

    1. Chia right (≥ start, tăng) và left (< start, tăng).
    2. Phục vụ right tăng dần.
    3. Nếu còn left: đi tới disk_max (cộng |disk_max - cur|), nhảy về 0 (cộng disk_max), rồi phục vụ left tăng dần từ 0.
    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]. 50→82→140→170 (=120), →199 (=29), nhảy →0 (=199), 0→43 (=43). Tổng = 120+29+199+43 = 391.

    • Đị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:

    391

    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 199 (29), nhảy về 0 (cộng 199). Từ 0 phục vụ left tăng: 0→43 (43). Tổng = 120+29+199+43 = 391.

    Đang tải editor...