MPILOT – SPOJ

Đề bài: http://vn.spoj.com/problems/MPILOT/

Thuật toán:

  • Đây là bài tập về thuật toán Heap cơ bản
  • Ta đưa yêu cầu bài toán thành chọn các lái phụ có chênh lệch giữa lương lái chính và lương lái phụ là lớn nhất mà vẫn đảm bảo yêu cầu có thể ghép được n/2 cặp mà tuổi lái phụ < lái chính
  • Heap sẽ lưu độ chênh lệch giữa lương lái phục và chính của mọi người
  • Duyệt i=1..n, đẩy i vào, nếu i lẻ thì lấy ở heap ra 1 thằng làm lại phụ
  • Các bạn hãy đọc code để rõ hơn

Code: [xem code]

const   fi='';
        fo='';
        maxn=10000+3;
var     p,h:array[1..maxn] of longint;
        i,j,n,res,sum:longint;
        a,c:array[1..maxn] of longint;
        nh:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i],c[i]);
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
function tinh(x:longint):longint;
begin
        exit(a[x]-c[x]);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and ( tinh(h[j+1]) > tinh(h[j]) ) then inc(j);
        if tinh(h[i]) < tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:= i div 2;
        if i>1 then
        if tinh(h[i]) > tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        upheap(nh);
end;
procedure process;
begin
        for i:=1 to n do
                begin
                        inc(sum,a[i]);
                        push(i);
                        if i mod 2 = 1 then inc(res,tinh(pop) );
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(sum-res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Comments

  1. cho em hỏi tại sao phải i mod 2=1, em ko hiểu chỗ đó

    • Mỗi khi heap có lẻ phi công (i mod 2 = 0) thì mình phải lấy ra ngay thằng tốt nhất để làm lái phụ. Nếu mà không lấy ra ngay thì sẽ không thỏa mãn điểu kiện tuổi lái chính > tuổi lái phụ.

      Bạn nên nhớ đề bài có đoạn “Các phi công sắp tăng dần theo tuổi.”

      Bạn suy nghĩ thêm nhé…

Speak Your Mind

*