1 окт. 2012 г.

Задачка: Объём луж

На рельеф некоторой местности падает дождь, попадая в низменности он образует лужи и озерца.

Найти объём образовавшихся луж за время O(N).

замечание №1: силами поверхностного натяжения пренебречь.

замечание №2: рельеф задан целыми числами

например:
V([0, 0, 3, 6, 6, 10, 5, 5, 5, 7, 7, 4, 9, 9, 13, 12, 14, 4, 3, 0]) = 30.

5 комментариев:

Ruslan Cheremin комментирует...

Мне кажется, надо сначала добавить две высокие стенки по бокам. А потом вылить воду из чайника.

Сергей комментирует...

Интересная задача! Пришлось помучиться, но вроде бы решил.
Сначала наблюдение. После того, как дождик прошёл, поверхность (водно-земляная) будет
представлять собой ступеньки, идущие вверх, а затем ступеньки, идущие вниз (такая
ступенчатая горка). Возможны и 3 вырожденных случая: ступеньки, идущие только вверх,
ступеньки, идущие только вниз и отсутствие ступенек (ровная поверхность). От этого
наблюдения и будем плясать.
Идея алгоритма следующая. Пускаем двух наблюдателей: один идёт слева направо, а другой -
справа налево. Левый начинает карабкаться по ступенькам до тех пор, пока не окажется перед обрывом, после чего останавливается. Теперь правый также карабкается по ступенькам до тех пор, пока не достигнет обрыва и не остановится. Перед тем из наблюдателей, который находится ниже другого, располагается вода. Если они на одинаковом уровне (но ещё не встретились), то вода перед обоими. Тот, перед которым вода, начинает движение вплавь. А чтобы ему не было скучно, заодно измеряет глубину с помощью эхолота и вычисляет объём воды. Наконец, доплывает до берега и снова карабкается по ступенькам до тех пор, пока не достигнет обрыва и не остановится. Опять сравниваются высоты, на которых находятся наблюдатели, и тот, который располагается ниже (не выше), прыгает в водичку. И так далее, до тех пор, пока они, мокрые, но счастливые, не встретятся на самой высокой площадке. Там они могут сложить найденные объёмы воды и порадоваться жизни.
Вроде понятно объяснил. Ясно, что движению наблюдателей будет соответствовать обработка элементов массива с высотами справа и слева. Т. е. "сжигаем свечу" с обеих сторон, пока не сожжём окончательно.
Постараюсь в следующем комментарии выложить реализацию алгоритма.

Сергей комментирует...

static int volume(int[] m)
{
int j = m.length - 1;
if (j < 2)
return 0;
int i = 0, v = 0;
while (i < j && m[i] <= m[i+1]) //Левый карабкается по ступенькам
i++;
int max1 = m[i];
while (i < j && m[j] <= m[j-1]) //Правый карабкается по ступенькам
j--;
int max2 = m[j];
while (i < j)
{
int t;
if (max1 >= max2) //Если левый не ниже правого
{
while (i < --j && (t = max2 - m[j]) > 0) //Правый плывёт
v += t;
while (i < j && m[j] <= m[j-1]) //Правый карабкается по ступенькам
j--;
max2 = m[j];
}
else //Если правый выше левого
{
while (++i < j && (t = max1 - m[i]) > 0) //Левый плывёт
v += t;
while (i < j && m[i] <= m[i+1]) //Левый карабкается по ступенькам
i++;
max1 = m[i];
}
}
return v;
}

Shahen комментирует...

def solve(arr)
prev_height = -1
res = 0
cum = 0
arr.each do |height|
if height >= prev_height then
prev_height = height
res = res + cum
cum = 0
else
dh = (prev_height - height)
cum = cum + dh
end
end
res
end

puts solve([0, 0, 3, 6, 6, 10, 5, 5, 5, 7, 7, 4, 9, 9, 13, 12, 14, 4, 3, 0])

Vladimir Dolzhenko комментирует...

@Shahen

По началу мне показалось, что решение не верное, но и красивое. Но это не так


V([0, 4, 0, 2, 0] ) = 2

в вашем же случае будет 0, что есть не верно