H
hai6f2009
Chắc suất Đại học top - Giữ chỗ ngay!! ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Bài 1. Trò chơi với dãy số (3 điểm)
Bờm và Cuội hiện đang chơi một trò chơi mới có tên gọi là “trò chơi với dãy số”. Luật chơi của trò này như sau, với mỗi lần chơi Bờm đưa ra 2 dãy số nguyên dương A1, A2,…, AN; B1, B2, …, BN, các số này đều ≤100. Nhiệm vụ của Cuội là ghép các cặp số (Ai, Bj) sao cho mỗi số chỉ dùng đúng 1 lần và tổng lớn nhất của các cặp số là nhỏ nhất có thể. Nhiệm vụ của bạn là tìm giúp Cuội tổng lớn nhất của mỗi cặp là nhỏ nhất có thể trong mỗi lần chơi.
Dữ liệu vào: Cho trong file ghepcap.inp có cấu trúc như sau:
- Dòng 1: ghi số nguyên N ([TEX]1 \leg n \leg 100000[/TEX]).
- Dòng thứ i trong số N dòng tiếp theo ghi 2 số nguyên dương Ai và Bi.
Dữ liệu ra: ghi vào file ghepcap.out một số nguyên duy nhất là kết quả tìm được.
Ví dụ:
3
2 8
3 1
1 4
9
Đây là code của mình:
nó cho max=5. các bạn có thể cho mình biết mình sai ở chỗ nào và hướng dẫn mình sửa lại được không? Mình xin cảm ơn các bạn!
Bờm và Cuội hiện đang chơi một trò chơi mới có tên gọi là “trò chơi với dãy số”. Luật chơi của trò này như sau, với mỗi lần chơi Bờm đưa ra 2 dãy số nguyên dương A1, A2,…, AN; B1, B2, …, BN, các số này đều ≤100. Nhiệm vụ của Cuội là ghép các cặp số (Ai, Bj) sao cho mỗi số chỉ dùng đúng 1 lần và tổng lớn nhất của các cặp số là nhỏ nhất có thể. Nhiệm vụ của bạn là tìm giúp Cuội tổng lớn nhất của mỗi cặp là nhỏ nhất có thể trong mỗi lần chơi.
Dữ liệu vào: Cho trong file ghepcap.inp có cấu trúc như sau:
- Dòng 1: ghi số nguyên N ([TEX]1 \leg n \leg 100000[/TEX]).
- Dòng thứ i trong số N dòng tiếp theo ghi 2 số nguyên dương Ai và Bi.
Dữ liệu ra: ghi vào file ghepcap.out một số nguyên duy nhất là kết quả tìm được.
Ví dụ:
ghepcap.inp
2 8
3 1
1 4
ghepcap.out
9
Đây là code của mình:
Mã:
program ghepcap;
const fi='ghepcap.inp';
fo='ghepcap.out';
var f:text;
n,s,max,min:longint;
a,b:array[1..100000] of integer;
procedure enter;
var i:integer;
begin
assign(f,fi);reset(f);
readln(f,n);
for i:=1 to n do readln(f,a[i],b[i]);
close(f);
end;
procedure qsort(l,r:integer);
var k,tmp,i,j:integer;
begin
if l>=r then exit;
i:=l;j:=r;//x:=a[random(r-l+1)+l];
k:= (l+r)div 2;
repeat
while a[i]<a[k] do inc(i);
while a[j]>a[k] do dec(j);
if i<=j then
begin
tmp:=a[i];
a[i]:=a[j];
a[j]:=tmp;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure qsort2(l,r:integer);
var k,tmp,i,j:integer;
begin
if l>=r then exit;
i:=l;j:=r;//x:=a[random(r-l+1)+l];
k:= (l+r)div 2;
repeat
while b[i]<b[k] do inc(i);
while b[j]>b[k] do dec(j);
if i<=j then
begin
if i<j then
begin
tmp:=b[i];
b[i]:=b[j];
b[j]:=tmp;
inc(i);
dec(j);
end;
end;
until i<j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure gtln;
begin
if s>max then max:=s;
end;
procedure gtnn;
begin
if s<min then
begin
min:=s;
gtln;
end;
end;
procedure process;
var i,j,min,max:integer;
begin
for i:=1 to n do
for j:= n downto 1 do
begin
s:=s+a[i]+b[i];
gtnn;
s:=0;
end;
end;
procedure printresult;
begin
assign(f,fo);rewrite(f);
writeln(f,max);
close(f);
end;
BEGIN
enter;
qsort(1,n);
qsort2(1,n);
min:=maxlongint;
max:=-maxlongint;
process;
printresult;
END.
Last edited by a moderator: