ACMNB – spoj

Đề bài:

Thuật toán:

Thuật toán có thể suy ra từ cách làm thực tế. Nếu Tí làm tất cả 2n bài sẽ mất tổng thời gian là

12-yeulaptrinh.pwTuy nhiên Tí phải nhường lại n bài cho Tèo. Mỗi khi Tí nhường bài i cho Tèo, thời gian S sẽ giảm đi một lượng ci = ai – bi. Ta cần chọn n bài để Tí nhường cho Tèo sao cho thời gian S giảm đi nhiều nhất, tức là phải chọn n chỉ số i có c lớn nhất.

Code:

CONST   FI='';
        FO='';
        maxn=trunc(1e5)*8;
type    arr1    =array[1..maxn] of longint;
var     n,i,j   :longint;
        a,b,c   :arr1;
        ans     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        read(n);
        for i:=1 to 2*n do read(a[i],b[i]);
        close(input);
end;
procedure swap(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint; var a,b,c:arr1);
var     i,j,x,y     :longint;
begin
        i:=l;j:=r;
        x:=a[(l+r) div 2];
        y:=b[(l+r) div 2];
        repeat
                while (x>a[i])  do inc(i);
                while (x<a[j])  do dec(j);
                if i<=j then
                        begin
                                swap(a[i],a[j]);
                                swap(b[i],b[j]);
                                swap(c[i],c[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r,a,b,c);
        if j>l then qs(l,j,a,b,c);
end;
procedure process;
begin
        for i:=1 to 2*n do c[i]:=a[i]-b[i];
        qs(1,2*n,c,a,b);
        for i:= 1 to n do
                ans :=  ans+a[i];
        for i:=n+1 to 2*n do
                ans := ans+b[i];
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(ans);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Khuyên dùng

 

Speak Your Mind

*