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] Cấp phát bộ nhớ First-Fit

    Mô phỏng chiến lược cấp phát bộ nhớ First-Fit.

    Có nb khối nhớ trống với kích thước cho trước (đánh số 1..nb theo thứ tự nhập). Lần lượt có nr yêu cầu cấp phát kích thước. Với mỗi yêu cầu, First-Fit chọn khối đầu tiên (theo chỉ số tăng dần) còn đủ chỗ; sau khi cấp, kích thước còn lại của khối giảm đi đúng bằng yêu cầu. Nếu không khối nào đủ, yêu cầu thất bại (in -1).

    Thuật toán: giữ mảng dung lượng còn lại của các khối. Với mỗi yêu cầu, duyệt khối từ trái sang phải tìm khối đầu tiên avail ≥ req, cấp vào đó, in chỉ số khối (1-based); nếu không có in -1.

    Ví dụ: khối 100 500 200 300 600, yêu cầu 212 417 112 426. Kết quả: 2 5 2 -1.

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

      Dòng 1: nb rồi nb kích thước khối. Dòng 2: nr rồi nr kích thước yêu cầu. (Các số có thể trên nhiều dòng; đọc theo token.)

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

      1 ≤ nb, nr ≤ 1000; 1 ≤ kích thước ≤ 1000000.

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

      nr số nguyên cách nhau bởi dấu cách: chỉ số khối (1-based) được cấp cho mỗi yêu cầu, hoặc -1 nếu thất bại.

    Ví dụ:

    Đầu vào:

    5 100 500 200 300 600
4 212 417 112 426

    Đầu ra:

    2 5 2 -1

    Giải thích:

    Khối còn [100,500,200,300,600]. 212→khối2(500≥212)→còn288, in 2. 417→khối2 còn288<417, khối5=600≥417→in5, còn183. 112→khối2 còn288≥112→in2, còn176. 426→không khối nào đủ(100,176,200,300,183)→-1. Kết quả: 2 5 2 -1.

    Đang tải editor...