Bài tập  /  Bài đang cần trả lời

Viết chương trình pascal ACM SuperCoders

viết chương trình pascal ACM SuperCoders là đội tuyển huyền thoại của trường XYZ đã nhiều lần vô địch cuộc thi lập trình viên vũ trụ ACM Universe Final. Theo thể’ thức cuộc thi, mỗi đội tham dự chỉ có đúng 3 thành viên và được giao duy nhất một máy tính, chính vì vậy việc điều phối công việc vô cùng quan trọng. Trong đội SuperCoders, PHUONGHD - đội trưởng - là người nắm giữ vai trò đó. Đề thi ACM năm nay gồm có 2n bài đánh số từ 1 tới 2n. Bằng kỹ năng thiết kế thuật toán siêu việt, chỉ vài giây sau khi đọc đề, PHUONGHD đã có lời giải cho cả 2n bài. Vấn đề còn lại là phân công hai người còn lại lập trình bởi PHUONGHD không quen với thứ ngôn ngữ lập trình mới được đưa vào sử dụng tại cuộc thi. Do rất hiểu hai lập trình viên Tí và Tèo trong đội, PHUONGHD biết rằng bài thứ í nếu giao cho Tí làm sẽ mất ai giây, cũng bài đó nếu giao cho Tèo sẽ mất bi giây để hoàn thành (Với: 1 < í < 2n). Nhiệm vụ của bạn là hãy giúp PHUONGHD phân công cho hai lập trình viên, mỗi người làm đúng n bài sao cho tổng thời gian lập trình cả 2n bài là ít nhất. Dữ liệu: Vào từ file văn bản ACM.INP • Dòng 1 chứa số nguyên dương n < 4.105 • 2n dòng tiếp theo, dòng thứ í chứa hai số nguyên dương ai , bi< 100 cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản ACM.OUT một số nguyên duy nhất là tổng thời gian lập trình cả 2n bài theo phương án phân công tìm được. Ví dụ 40% số điểm ứng với các test có n < 1000 30% số điểm ứng với các test có n  [104 ,105 ] 30% số điể’m ứng với các test có n  [3.105 ,4.105 ] ACM.INP 2 2 1 3 2 5 3 1 2 ACM.OUT 8
1 trả lời
Hỏi chi tiết
131
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải quyết bài toán này, ta có thể sử dụng thuật toán Greedy. Ý tưởng của thuật toán như sau:

1. Đọc dữ liệu từ file ACM.INP.
2. Sắp xếp các bài theo thứ tự tăng dần của thời gian hoàn thành (ai + bi).
3. Phân công bài cho hai lập trình viên Tí và Tèo theo cách sau:
- Lập trình viên Tí sẽ làm các bài có thời gian hoàn thành nhỏ nhất.
- Lập trình viên Tèo sẽ làm các bài có thời gian hoàn thành lớn nhất.
- Lặp lại cho đến khi không còn bài nào để phân công.
4. Tính tổng thời gian lập trình cả 2n bài và ghi kết quả vào file ACM.OUT.

Dưới đây là code mẫu để giải bài toán này:

```pascal
program ACM_SuperCoders;

const
MAX_N = 4105;

type
Task = record
a, b: Integer;
end;

var
n: Integer;
tasks: array[1..2 * MAX_N] of Task;

procedure ReadInput;
var
i: Integer;
begin
ReadLn(n);
for i := 1 to 2 * n do
ReadLn(tasks[i].a, tasks[i].b);
end;

function CompareTasks(task1, task2: Task): Integer;
begin
Result := (task1.a + task1.b) - (task2.a + task2.b);
end;

procedure SortTasks;
var
i, j: Integer;
temp: Task;
begin
for i := 1 to 2 * n - 1 do
for j := i + 1 to 2 * n do
if CompareTasks(tasks[i], tasks[j]) > 0 then
begin
temp := tasks[i];
tasks[i] := tasks[j];
tasks[j] := temp;
end;
end;

function Min(a, b: Integer): Integer;
begin
if a < b then
Result := a
else
Result := b;
end;

function Max(a, b: Integer): Integer;
begin
if a > b then
Result := a
else
Result := b;
end;

function AssignTasks: Integer;
var
i: Integer;
totalTime: Integer;
begin
SortTasks;

totalTime := 0;
for i := 1 to n do
totalTime := totalTime + Max(tasks[i].a, tasks[2 * n - i + 1].b);

Result := totalTime;
end;

procedure WriteOutput(totalTime: Integer);
begin
WriteLn(totalTime);
end;

begin
ReadInput;
WriteOutput(AssignTasks);
end.
```

Sau khi chạy chương trình, kết quả sẽ được ghi vào file ACM.OUT.
0
0
Dannz
22/11/2023 21:13:00
+5đ tặng
program ACM;
const
  maxN = 400000;
var
  n, i, j: longint;
  a, b, f: array[0..maxN] of int64;
  x: array[0..maxN] of longint;
procedure enter;
var
  i: longint;
begin
  readln(n);
  for i := 1 to 2*n do readln(a[i], b[i]);
end;
procedure sort(l, r: longint);
var
  i, j: longint;
  x, y, z: int64;
begin
  i := l; j := r;
  x := a[(l + r) div 2] - b[(l + r) div 2];
  repeat
    while a[i] - b[i] < x do inc(i);
    while x < a[j] - b[j] do dec(j);
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      y := b[i]; b[i] := b[j]; b[j] := y;
      z := x[i]; x[i] := x[j]; x[j] := z;
      inc(i); dec(j);
    end;
  until i > j;
  if l < j then sort(l, j);
  if i < r then sort(i, r);
end;
procedure solve;
var
  i, j: longint;
begin
  sort(1, 2*n);
  for i := 1 to 2*n do
  begin
    f[i] := f[i-1] + a[i];
    x[i] := x[i-1] + 1;
    if (x[i-1] < n) and (f[i] > f[i-1] + b[i]) then
    begin
      f[i] := f[i-1] + b[i];
      x[i] := x[i-1];
    end;
  end;
  writeln(f[2*n]);
end;
begin
  assign(input, 'ACM.INP'); reset(input);
  assign(output, 'ACM.OUT'); rewrite(output);
  enter;
  solve;
  close(input); close(output);
end.
 

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm
Trắc nghiệm Lập trình Lớp 9 mới nhất

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường

Học ngoại ngữ với Flashcard

×
Trợ lý ảo Trợ lý ảo
×
Gia sư Lazi Gia sư