Bài 3: Đoạn đường đẹp nhất (Đề thi Tin học 10 –
Olympic 30/4/2013)
Trong thời gian vừa qua, người dân ở hành
tinh Alpha đã vui mừng chào đó sự xuất hiện của con đường mới XYZ. Được đầu tư
rất nhiều nguồn vốn, con đường này được coi là con đường đẹp nhất hành tinh.
Những tòa nhà chỉ ở một bên đường với độ cao khác nhau. Theo các giáo sư, đoạn
đường đẹp nhất là đoạn đường ở đó độ cao trung bình của các tòa nhà bằng K. Cụ
thể, có N tòa nhà nằm cạnh nhau ở một bên của con đường. Tòa nhà thứ i tính từ
đầu đường có độ cao là Ai.
Yêu
cầu: Hãy tìm đoạn đường dài nhất
chứa các tòa nhà liên tiếp sao cho chúng có độ cao trung bình là K.
Dữ
liệu vào: cho trong ROAD.INP:
-
Dòng 1:
ghi hai số nguyên N và K (1≤ N ≤ 105; 0 ≤ K ≤ 109).
-
N dòng
tiếp theo, dòng thứ i ghi số nguyên Ai (0 ≤ Ai ≤ 109).
Kết
quả ra: ghi vào ROAD.OUT:
Nếu không tìm được đoạn nào có các tòa nhà có
độ cao trung bình là K thì ghi ra một số 0 duy nhất. Ngược lại, ghi ra hai số
u, v với ý nghĩa: u là vị trí bắt đầu của đoạn đường và v là độ dài đoạn đường.
Nếu có nhiều đáp án thì ghi ra đáp án có u nhỏ nhất.
Ví
dụ:
ROAD.INP
|
ROAD.OUT
|
4 5
2
4
5
6
|
2 3
|
ĐÁP ÁN - HƯỚNG DẪN GIẢI
Cách 1: O(N^3)
Vector nghiệm: (i, j)
Procedure isOK(i, j: integer); //O(N)
Var p, q: integer; S:longint;
Begin
S:=0;
For
p:=i to j do
S:=
S + a[p];
If
S div (i-j+1) = K then
If
j-i+1 >v then
Begin u:=i; v:=
j-i+1; End;
End;
Procedure Solve; //O(N^2)
Var i, j: integer;
Begin
Max:=0;
For i:=1 to N-1 do
For
j:=i+1 to N do
isOK(i,j);
End;
Nhận xét: với độ phức tạp O(N^3) thì chỉ phủ
hợp với N<10^3.
Cách 2: O(N^2)
Procedure isOK(i, j: integer); //O(1)
Begin
If
(S[j] – S[i-1]) div (i-j+1) = K then
If
j-i+1 >v then
Begin u:=i; v:=
j-i+1; End;
End;
Procedure Solve; //O(N^2)
Var i, j: integer;
Begin
Max:=0;
For i:=1 to N-1 do
For
j:=i+1 to N do
isOK(i,j);
End;
Nhận xét: với độ phức tạp O(N^2) thì chỉ phủ
hợp với N<30 000, nhưng vẫn chưa đạt đến N = 10^5 của đề bài.
Cách 3: O(NlogN)
Procedure isOK(j: integer); //O(logN)
Var i0: integer;
Begin
i0:=BinarySearch(S[j]
– K(j+1)) then //O(logN)
if
i0>0 then
If
j-i0+1 >v then
Begin u:=i0; v:=
j-i0+1; End;
End;
Procedure Solve; //O(N)
Var j: integer;
Begin
Max:=0;
For j:=1 to N do
isOK(j);
End;
Begin //main program
T[i].value = S[i-1] + K.i;
T[i].i = i; //với mọi i, O(N)
QuickSort(T) //O(NlogN)
Solve; // O(NlogN)
End.
Nhận xét: độ phức tạp O(NlogN), chạy tốt với N = 10^7.
Cách 4: O(N).
Tuy nhiên không khả thi do vấn đề bộ nhớ.
