На рельеф некоторой местности падает дождь, попадая в низменности он образует лужи и озерца. Найти объём образовавшихся луж за время 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 комментариев:
Мне кажется, надо сначала добавить две высокие стенки по бокам. А потом вылить воду из чайника.
Интересная задача! Пришлось помучиться, но вроде бы решил.
Сначала наблюдение. После того, как дождик прошёл, поверхность (водно-земляная) будет
представлять собой ступеньки, идущие вверх, а затем ступеньки, идущие вниз (такая
ступенчатая горка). Возможны и 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;
}
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])
@Shahen
По началу мне показалось, что решение не верное, но и красивое. Но это не так
V([0, 4, 0, 2, 0] ) = 2
в вашем же случае будет 0, что есть не верно
Отправить комментарий