Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước
được gọi là đoạn. Cho dãy gồm N số tự nhiên. Tìm đoạn ngắn nhất có tổng các
phần tử bằng giá trị K cho trước.
TDOAN.INP
|
TDOAN.OUT
|
21 17
0 2
3 2 10
1 5
5 6 12
20 30 14 8 0
11 0 6 0 0
5
|
16 3
|
Dữ liệu vào: tệp văn bản TDOAN.INP
Dòng thứ nhất: hai số tự nhiên N và K,
1 £ N £ 2000.
1 £ N £ 2000.
Từ dòng thứ hai trở đi: các phần tử của dãy.
Dữ liệu ra: tệp văn bản TDOAN.OUT
Chứa một dòng duy nhất gồm hai số tự nhiên d – chỉ số đầu đoạn và L – số phần tử trong
đoạn (chiều dài đoạn). Nếu vô nghiệm thì ghi 0 0.
Trong các tệp, dữ liệu trên cùng dòng cách nhau qua dấu cách.
Thuật toán
Ta giải bằng kĩ thuật cửa
sổ trượt như sau. Xét đoạn a[i..j] với tồng S = a[i] + a[i+1] + … + a[j], i
£
j. Đoạn này được gọi là cửa sổ. Ta cho cửa sổ này trượt dần qua phải và xét ba
tình huống sau đây.
1) (S = K): ta ghi nhận điểm đầu i và độ dài đoạn là j-i+1.
Nếu độ dài này nhỏ hơn độ dài LMin thì ta cập nhật lại các giá trị iMin và Lmin
(thủ tục Update). Rồi tiếp tục xét cửa sổ mới là a[i+1..j] .
2) (S < K): Ta dịch đầu phải của cửa sổ từ j sang j+1,
giữ nguyên đầu trái (thủ tục Right).
3) (S > K): Ta co đầu trái của cửa sổ từ i thành i+1 (thủ
tục Left).
Ta đặt phần tử a[n+1] = 0 làm lính canh.
(****************************************
TONG DOAN - Doan ngan
nhat
co tong K
****************************************)
program TDoan;
uses crt;
const
mn = 2001; bl = #32;
fn = 'TDOAN.INP'; gn =
'TDOAN.OUT';
type mw1 = array[0..mn] of word;
var f,g: text;
n,k: word;
a: mw1;
iMin, LMin: word;
iLeft,iRight: word;
sum: word;
procedure Doc;
var i: word;
begin
assign(f,fn); reset(f);
readln(f,n, k);
for i := 1 to n do
read(f,a[i]);
close(f);
end;
procedure Left;
begin
sum := sum - a[iLeft];
iLeft := iLeft + 1;
if (iLeft > iRight)
then
begin iRight := iLeft;
sum := a[iLeft]; end;
end;
procedure Right;
begin iRight := iRight +
1; sum := sum + a[iRight]; end;
procedure Update;
begin
if (LMin > iRight -
iLeft + 1) then
begin iMin := iLeft;
LMin := iRight - iLeft + 1; end;
Left;
end;
procedure XuLi;
begin
iLeft := 1; iRight :=
iLeft;
LMin := n + 1; sum :=
a[1];
repeat
if (sum = k) then
Update
else if (sum < k)
then Right
else { sum > k
} Left;
until (iRight > n);
if (LMin = n+1) then
LMin := 0;
end;
procedure Ghi;
begin
assign(g,gn); rewrite(g);
writeln(g,iMin,bl,LMin); close(g);
end;
BEGIN
Doc; XuLi; ghi;
END.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét