Bài toán: Bố trí phòng học

Mô tả

Có n phòng học chuyên đề và k nhóm học sinh, được đánh số từ nhỏ đến lớn.

Cần xếp k nhóm trên vào một số phòng sao cho:

• Mỗi nhóm được xếp vào đúng một phòng.
• Mỗi phòng dùng nhiều nhất cho một nhóm.
• Nếu nhóm có số hiệu nhỏ hơn được xếp vào phòng số i thì nhóm có số hiệu lớn hơn phải được xếp vào một phòng có số hiệu lớn hơn i.
• Một nhóm chỉ có thể xếp vào phòng có đủ số ghế.

Gọi a[i] là số ghế của phòng thứ i, b[j] là số học sinh của nhóm thứ j.

Nếu xếp nhóm j vào phòng i thì số ghế thừa là a[i] - b[j] (điều kiện a[i] >= b[j]).

Hãy chọn một phương án bố trí sao cho tổng số ghế thừa của các phòng được sử dụng là nhỏ nhất.

Dữ liệu vào

Đọc từ tệp Botriphonghoc.inp:

• Dòng 1: hai số nguyên dương n, k (1 <= k <= n <= 10000)
• Dòng 2: n số nguyên a[i] (1 <= a[i] <= 1000) — số ghế của các phòng
• Dòng 3: k số nguyên b[j] (1 <= b[j] <= 1000) — số học sinh của các nhóm

Dữ liệu ra

Ghi ra tệp Botriphonghoc.out một số nguyên duy nhất: tổng số ghế thừa nhỏ nhất.

Ví dụ

Botriphonghoc.inp

5 3
25 30 35 40 45
30 25 40

Botriphonghoc.out

10

Giải thích ví dụ

Một cách bố trí tối ưu là:

• Nhóm 1 (30 học sinh) vào phòng 3 (35 ghế), thừa 5 ghế
• Nhóm 2 (25 học sinh) vào phòng 2 (30 ghế), thừa 5 ghế
• Nhóm 3 (40 học sinh) vào phòng 4 (40 ghế), thừa 0 ghế

Tổng số ghế thừa là 5 + 5 + 0 = 10.

Lưu ý rằng thứ tự nhóm phải tương ứng với thứ tự phòng được chọn.

Gợi ý

Đây là bài toán quy hoạch động:

• dp[i][j]: chi phí nhỏ nhất khi xét i phòng đầu tiên và đã xếp được j nhóm đầu tiên
• Có thể:
  • bỏ qua phòng i
  • hoặc dùng phòng i để xếp cho nhóm j nếu a[i] >= b[j]

Có thể tối ưu bộ nhớ xuống O(k).