Đề 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à
Tuy 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 (xj;
if il 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.
[Chú ý: Đừng nhầm lẫn Java với JavaScript, vì JavaScript là một ngôn ngữ hoàn toàn khác được sử dụng cho lập trình web – chúng ta sẽ nói về nó trong bài viết sau].
Tiềm năng kiếm tiền: 
Objective-C/ Cocoa
Tiềm năng kiếm tiền:
Recent Comments