HỌC TIN CÙNG THỦ KHOA

Đề bài: Có n phòng học chuyên đề và k nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp k nhóm trên vào n phòng học sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ, nhóm có số hiệu lớn phải được xếp vào phòng có số hiệu lớn. Với mỗi phòng có chứa học sinh, các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì lấy vào cho đủ ghế. Biết phòng i có a(i) ghế, nhóm j có b(j) học sinh. Hãy chọn 1 phương án bố trí sao cho tổng số lần chuyển ghế ra và vào là ít nhất.

Mời các bạn download tại: Click here

const fi = 'CAULACBO.INP';
      fo = 'CAULACBO.OUT';
      MAXN = 1000;
      MAXK = 1000;
      oo = MAXINT;
var n, k: integer;
    v: array [1..MAXK, 1..MAXN] of integer;
    L: array [1..MAXK, 1..MAXN] of integer;
    a: array [1..MAXN] of integer;
    b: array [1..MAXK] of integer;
    f: text;

procedure Nhap;
var i, j: integer;
begin
        assign(f, fi); reset(f);
        readln(f, n, k); //n phong hoc va k nhom hoc sinh
        for i:= 1 to n do read(f, a[i]); //doc so ghe tung phong
        for i:= 1 to k do read(f, b[i]); //doc so hoc sinh tung nhom

        // Goi L[i, j] la so cach chuyen ghe it nhat khi xep cac nhom 1..i vao
        // cac phong hoc 1..j thoa man yeu cau de bai
        for i:=1 to k do
            for j:=1 to n do v[i,j]:= abs(b[i] - a[j]);
        // v[i,j] la do lech giua nhom hoc sinh j va so ghe phong i
        close(f);
end;

function sum(i: integer): integer;
var s, t: integer;
begin
        s:= 0;
        for t:= 1 to i do
                s:= s + v[t, t];
        exit(s);
end;

function min(a, b: integer): integer;
begin
        if a < b then exit(a)
                else exit(b);
end;

procedure QHD;
var i, j, t: integer;
begin
        // L[i, j] la so lan chuyen ghe it nhat khi xep
        // nhom hoc sinh 1..i vao cac phong 1..j

        // Bai toan con co ban:

        L[1, 1]:= sum(1);

        for j:= 2 to n do
        begin
                L[1, j]:= +oo;
                for t:= 1 to j do
                if L[1, j] > abs(b[1] - a[t]) then
                        L[1, j]:= abs(b[1] - a[t]);
        end;

        for i:= 2 to k do
                for j:= 1 to n do
                    if i = j then L[i, j]:= sum(i)
                    else
                    begin
                        if i > j then L[i, j]:= +oo
                           else // i < j
                                L[i, j]:= min(L[i-1, j-1] + v[i, j],
                                              L[i, j-1]);
                    end;
end;

procedure TruyVet(i, j: integer);
var t: integer;
begin
        if i = 1 then
        begin
                if j = 1 then
                begin
                        writeln(f, 'Chon nhom hoc sinh 1 xep vao phong 1');
                        exit;
                end;
                // j > 1
                for t:= 1 to j do
                        if L[i, j] = abs(b[i] - a[t]) then
                        begin
                             writeln(f, 'Chon nhom hoc sinh 1 xep vao phong ', t);
                             exit;
                        end;

        end;

        if j = 1 then exit;

        if L[i, j] = L[i-1, j-1] + v[i, j] then
        begin
                TruyVet(i-1, j-1);
                writeln(f, 'Chon nhom hoc sinh ', i, ' xep vao phong ', j);
        end
                else TruyVet(i, j-1);
end;

procedure InKQ;
begin
        assign(f, fo); rewrite(f);
        writeln(f, L[k, n]);
        if L[k, n] = +oo then writeln(f, 'Khong co cach xep hop ly')
                else TruyVet(k, n);
        close(f);
end;

BEGIN
        Nhap;
        QHD;
        InKQ;
END.