Bài 5.1. Băng nhạc
Người ta cần ghi N bài hát, được mã số
từ 1 đến N, vào một băng nhạc có thời lượng tính theo phút đủ chứa toàn bộ các
bài đã cho. Với mỗi bài hát ta biết thời lượng phát của bài đó. Băng sẽ được
lắp vào một máy phát nhạc đặt trong một siêu thị. Khách hàng muốn nghe bài hát
nào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ i trên băng, máy
xuất phát từ đầu cuộn băng, quay băng để bỏ qua i – 1 bài ghi trước bài đó.
Thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được tính là như
nhau. Tính trung bình, các bài hát trong một ngày được khách hàng lựa chọn với
số lần (tần suất) như nhau. Hãy tìm cách ghi các bài trên băng sao cho tổng
thời gian quay băng trong mỗi ngày là ít nhất.
Dữ liệu
vào được ghi trong tệp văn bản tên BANGNHAC.INP.
-
Dòng đầu tiên là
số tự nhiên N cho biết số lượng bài hát.
-
Tiếp đến là N số
nguyên dương thể hiện dung lượng tính theo phút của mỗi bài. Mỗi đơn vị dữ liệu
cách nhau qua dấu cách.
BANGNHAC.INP
3
7 2 3
|
BANGNHAC.OUT
2 2
3 5
1 12
19
|
Thí dụ dưới đây cho biết có N = 3 bài hát:
-
Bài 1 phát trong
thời gian 7 phút.
-
Bài 2 phát trong
thời gian 2 phút.
-
Bài 3 phát trong
thời gian 3 phút.
Dữ liệu ra
được ghi trong tệp văn bản BANGNHAC.OUT theo dạng thức sau:
-
N dòng đầu tiên thể hiện trật tự
ghi bài hát trên băng: m ỗi dòng gồm hai số nguyên dương j và d cách nhau bởi dấu
cách, trong đó j là mã số của bài hát
cần ghi, d là thời gian tìm và phát
bài đó theo trật tự ghi này.
-
Dòng thứ n + 1 ghi tổng số thời gian quay băng
nếu mỗi bài hát được phát một lần trong ngày.
Với thí dụ trên, kết quả thu được sẽ như sau:
-
Cần ghi lần lượt trên băng các bài theo trật tự : bài 2, bài 3, bài 1;
-
Để tìm và phát bài 2 cần 2 phút;
-
Để tìm và phát bài 3 cần 5 phút;
-
Để tìm và phát bài 1 cần 12 phút;
-
Tổng thời gian để tìm và phát mỗi bài một lần là: 19
phút.
Thuật toán
Giả sử ta có ba bài hát
với số phút lần lượt như sau:
Mã số bài hát
|
j
|
k
|
l
|
Thời gian phát
|
7
|
2
|
3
|
Ta xét vài tình huống ghi băng để rút ra kết luận cần thiết.
Trật tự ghi trên
băng
(x, y, z)
|
Thời gian phát
t(x) + t(y) + t(z); t(i): thời gian tìm và phát bài i
|
(j
, k
, l)
|
(7) + (7 + 2) + (7 + 2 + 3) = 28 phút
|
(j
, l
, k)
|
(7) + (7 + 3) + (7 + 3 + 2) = 29 phút
|
(k
, j
, l)
|
(2) + (2 + 7) + (2 + 7 + 3) = 23 phút
|
(k
, l
, j)
|
(2) + (2 + 3) +
(2 + 3 + 7) = 19 phút (phương án tối ưu)
|
(l
, j
, k)
|
(3) + (3 + 7) + (3 + 7 + 2) = 25 phút
|
(l
, k
, j)
|
(3) + (3 + 2) + (3 + 2 + 7) = 20 phút
|
Vậy phương án tối ưu sẽ là (k , l , j): ghi bài 2 rồi đến bài 3, cuối cùng ghi bài 1. Tổng
thời gian theo phương án này là 19 phút.
Để có phương án tối ưu ta chỉ cần ghi băng theo trật tự tăng dần của
thời lượng. Bài toán được cho với giả thiết băng đủ lớn để ghi được toàn bộ các
bài. Dễ dàng sửa chương trình để vận dụng cho trường hợp dung lượng tăng hạn
chế trong M phút. Chương trình sắp xếp dữ liệu theo chỉ dẫn.
(* Pascal *)
(*----------------------
BangNhac.pas
-----------------------*)
program
BangNhac;
uses crt;
const
MN =
200; BL = #32; {dau cach}
fn =
'Bangnhac.inp'; gn = 'Bangnhac.out';
var
a,id: array[1..MN] of integer;
f, g: text;
n: integer;
{------------------------------------
Doc du lieu tu
input file vao mang a
-------------------------------------}
procedure Doc;
var i,k:
integer;
begin
assign(f,fn);
reset(f); read(f,n);
for i := 1 to
n do read(f,a[i]);
close(f);
end;
{---------------------------------
Khoi tri mang chi dan id
quan li sap tang theo chi dan
----------------------------------}
procedure InitID;
var i:
integer;
begin
for i := 1 to n do id[i] := i;
end;
{---------------------------------
Sap tang theo chi dan
----------------------------------}
procedure
IDQuickSort(d,c: integer);
var i, j, m,
x: integer;
begin
i := d;
j := c;
m := a[id[(i+j) div 2]]; {phan tu giua}
while i <=
j do
begin
while
a[id[i]] < m do inc(i);
while
a[id[j]] > m do dec(j);
if i
<= j then
begin
x := id[i];
id[i] := id[j];
id[j] := x;
inc(i); dec(j);
end;
end;
if d < j
then IDQuickSort(d,j);
if i < c
then IDQuickSort(i,c);
end;
{-------------------------------
Ghi ket
qua vao output file
--------------------------------}
procedure Ghi;
var i, t, tt:
longint;
begin
assign(g,gn);
rewrite(g);
t := 0; {thoi gian
tim va phat 1 bai}
tt := 0; {tong thoi gian cho n bai}
for i := 1 to n do
begin
t := t + a[id[i]];
tt := tt + t;
writeln(g,id[i],BL,t);
end;
writeln(g,tt);
close(g);
end;
BEGIN
Doc; InitID; IDQuickSort(1,n); Ghi;
END.
Không có nhận xét nào:
Đăng nhận xét