Решение (Поляков К.Ю.)
1)
Сначала поймем, что требуется найти.
Предположим, что все результаты измерения
записаны в массив:
Нужно найти пару элементов с максимальной суммой, отстоящих друг от друга не менее, чем на K (в данной задаче K = 7) позиций в массиве, то есть разность их индексов должна быть больше или равна K. Предположим, что второй элемент в паре (стоящий ближе к концу массива) имеет индекс i. Тогда соответствующий первый элемент из той же пары нужно искать в диапазоне индексов от 1 до i-K (см. желтую зону на рисунке).
Для элемента с индексом i наибольшую сумму даст наибольший элемент из этого диапазона. Его можно найти эффективно в процессе ввода элементов следующим образом. Предположим, что мы уже знаем максимальный элемент (обозначим его max) в диапазоне индексов от 1 до i-K-1. При переходе к следующему значению i нам нужно найти максимум из элементов с индексами от 1 до i-K, то есть к уже рассмотренным элементам (для которых мы знаем максимум max) добавляется один элемент Buf[i-K], выделенный голубым цветом на рисунке:
Итак, если второй элемент в паре имеет индекс i, то в качестве значения первого элемента мы можем взять найденное выше значение max. Из всех таких пар (при всех i от K+1 до N) нужно выбрать пару с максимальной суммой (будем хранить её в переменной maxSum):
if max + Buf[i] >
maxSum then
maxSum := max + Buf[i]; Организуем эффективное хранение данных. Когда мы читаем из входного потока очередной элемент (в массиве он хранился в элементе с индексом i), то на этом шаге нужно добавить к элементам, среди которых ищется максимум, элемент, прочитанный на K шагов раньше, то есть, нужно хранить (в массиве) только K предыдущих элементов. Размер этого массива K не зависит от N, которое может быть очень большим. После использования значения с номером i-K для поиска максимума нужно запомнить в массиве только что прочитанное значение.
Структура данных, с помощью которой можно решить эту задачу, называется очередью. Элементы в очередь добавляются с одного конца (это будет конец массива), а извлекаются – с другого (с начала массива). После удаления первого элемента (который «включается» в поиск максимума) все элементы очереди, начиная со второго, сдвигаются на одну позицию к началу массива, а в последний (освободившийся) элемент записывается только что прочитанное значение (оно хранится в переменной elem):
Сначала нужно заполнить очередь: прочитать в неё первые K измеренных значений:
var Buf: array[1..K]
of integer;
...
for i:=1 to K do
read(Buf[i]);
Затем
читаем и обрабатываем оставшиеся N-K значений:
for i:=K+1 to N do
begin
read(elem);
...
end;
На
первом шаге этого цикла записываем в переменную max первый элемент очереди, а в переменную maxSum – сумму max и только что прочитанного значения elem; на остальных шагах цикла обновляем эти максимальные
значения:
if i = K+1 then begin
max := Buf[1];
maxSum := Buf[1] + elem;
end
else begin
if Buf[1] > max then
max := Buf[1];
if max+elem > maxSum then
maxSum := max + elem;
end
После
этого нужно сдвинуть все элементы очереди на одну позицию к началу (удалить уже
использованный первый элемент) и добавить в конец очереди новое значение elem:
for j:=1 to K-1 do
Buf[j] := Buf[j+1];
Buf[K]
:= elem;
В конце цикла нужное значение оказывается в
переменной maxSum.
Приведём полное правильное решение, эффективное как по времени выполнения (оно
линейно зависит от N), так и по используемой памяти (не зависит от N):
const K = 7;
var i, j, N, max, maxSum, elem: integer;
Buf: array[1..K] of integer;
begin
read(N);
{ заполняем очередь }
for i:=1 to K do read(Buf[i]);
{ обрабатываем оставшиеся данные }
for i:=K+1 to N do begin
read(elem);
if i = K+1 then begin { начальные значения max и maxSum }
max := Buf[1];
maxSum := Buf[1] + elem;
end
else begin
if Buf[1] > max then max := Buf[1];
if max+elem > maxSum then
maxSum := max + elem;
end;
{ обработка очереди }
for j:=1 to K-1 do { сдвиг очереди }
Buf[j] := Buf[j+1];
Buf[K] := elem; { добавить элемент в очередь }
end;
writeln(maxSum);
end.
Комментариев нет:
Отправить комментарий