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 LOOK

    Thuật toán lập lịch đĩa LOOK. Đầu đọc bắt đầu ở vị trí start, ban đầu di chuyển theo hướng cho trước (U = lên/tăng dần, D = xuống/giảm dần). Khác SCAN, LOOK không đi tới biên đĩa mà chỉ đi tới yêu cầu xa nhất theo hướng hiện tại rồi đảo chiều.

    Thuật toán:

    1. Tách các yêu cầu thành hai nhóm: nhỏ hơn start và lớn hơn hoặc bằng start.
    2. Nếu hướng = U: phục vụ các yêu cầu ≥ start theo thứ tự tăng dần (tới yêu cầu lớn nhất), rồi đảo chiều phục vụ các yêu cầu < start theo thứ tự giảm dần.
    3. Nếu hướng = D: phục vụ các yêu cầu ≤ start theo thứ tự giảm dần, rồi đảo chiều phục vụ các yêu cầu > start theo thứ tự tăng dần.
    4. Tổng quãng đường = tổng trị tuyệt đối các bước di chuyển của đầu đọc.

    In ra tổng quãng đường di chuyển của đầu đọc.

    Ví dụ: start=50, hướng U, yêu cầu [82,170,43,140,24,16,190]. Đi lên 82,140,170,190 (tới 190), rồi xuống 43,24,16. Tổng = (190-50)+(190-16)=140+174=314.

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

      Dòng đầu: start hướng N (hướng là U hoặc D, N là số yêu cầu). Dòng tiếp: N vị trí yêu cầu.

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

      0 ≤ start ≤ 10^9; 1 ≤ N ≤ 100000; 0 ≤ vị trí ≤ 10^9.

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

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

    Ví dụ:

    Đầu vào:

    50 U 7
82 170 43 140 24 16 190

    Đầu ra:

    314

    Giải thích:

    Hướng lên: phục vụ ≥50 tăng dần 82,140,170,190 (tới 190), rồi đảo chiều xuống 43,24,16. Tổng = (190-50)+(190-16)=140+174=314.

    Đang tải editor...