что это за жадный подход?

введите здесь описание изображенияпредположим, что у нас есть несколько 2D-боксов в контейнере, окруженном водой. К сожалению, в левой боковой стенке контейнера есть отверстие. Высота этого отверстия больше высоты всех ящиков. Длина всех ящиков 1 м, а их высота целое число. Все ящики ставятся в одну линию. За каждую секунду количество воды, проходящей через контейнер, составляет один квадратный метр. (убедитесь, что наша проблема находится в 2D-контексте). Мы хотим узнать, сколько времени потребуется, чтобы данный ящик оказался на один метр под водой. есть ли какой-нибудь жадный алгоритм для эффективного решения этой проблемы?


algorithm greedy
person user3070752    schedule 13.11.2014    source источник
comment
На самом деле это больше похоже на проблему интегрального исчисления/скорости изменения, чем на что-либо другое.   -  person Matt G.    schedule 13.11.2014
comment
помните, что высота всех ящиков не одинакова, и мы не можем легко рассчитать время, необходимое для покрытия ящика водой на 1 квадратный метр.   -  person user3070752    schedule 13.11.2014
comment
Вам не нужен жадный алгоритм, это можно решить за один проход. Но вы просили жадный алгоритм, а я не могу его придумать.   -  person Mooing Duck    schedule 13.11.2014
comment
Подождите, я предположил, что вода попадает в отверстие. Это правильно? Вода поступает через отверстие с левой стороны? Я также предполагаю, что высота ящиков представляет собой целое количество метров?   -  person Mooing Duck    schedule 13.11.2014
comment
да, он проходит через отверстие, а высота - целое число   -  person user3070752    schedule 13.11.2014
comment
Способна ли вода обтекать ящики, или ящик создаст эффект запруды, позволяя воде заполниться слева от него, прежде чем вылиться?   -  person MooseBoys    schedule 13.11.2014
comment
@MooseBoys: 2D-контекст отвечает на первый вопрос. Все ящики выстроены в одну линию, я предполагаю, что они лежат ровно на дне и, вероятно, не соприкасаются, что вызывает эффект запруды. Я также предполагаю, что они неподвижны/негибки.   -  person Mooing Duck    schedule 13.11.2014
comment
Ой! Я предполагал, что ящики не соприкасаются, а вода должна покрывать только дно. Теперь я вижу, что мы должны получить один метр воды над произвольной коробкой! Это... немного сложнее. Только немного однако. Однако мое замешательство остается, я не вижу, какой выбор нужно сделать, и, следовательно, как будет применяться жадный алгоритм. Я могу только понять, как быстро найти ответ :/   -  person Mooing Duck    schedule 13.11.2014
comment
если вы считаете, что у этой проблемы есть быстрый ответ, дайте его. Но я думаю, вы должны рассчитать время, необходимое конкретному ящику, чтобы заполнить все предыдущие ящики и следующие ящики, пока вода не сможет подняться над ним, позаботьтесь о том, чтобы все ящики касались своих соседей.   -  person user3070752    schedule 13.11.2014
comment
@amirveyseh Когда в i-м ящике есть вода на 1 метр, не правда ли, что все i-1 ящики до него наполнились и переполнились? Итак, вы знаете, что общее количество воды, поступившей в систему = вместимость первых i-1 ящиков + 1 метр воды. Итак, вы выполняете один проход линейной предварительной обработки, после чего можете отвечать на каждый запрос за постоянное время.   -  person Pradhan    schedule 13.11.2014
comment
@Pradhan наши ящики сплошные, поэтому вода может накапливаться только над j-м ящиком только тогда, когда j-1-й и j+i-й ящики выше j-го ящика. Поэтому для произвольного ящика мы должны вычислить это пространство, которое Я называю их хорошо!И, конечно, время связано с соседними скважинами...   -  person user3070752    schedule 13.11.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, что этот алгоритм может решить это за O (n).

из i-го ящика мы сначала идем в конец строки, чтобы найти первый ящик, который выше i-го ящика. так как разница между высотами всех ящиков составляет не менее 1 метра, поэтому вода не может пройти дальше, чем это поле. Затем мы переходим от i-го поля к началу строки. Мы сохраняем высоту i-го поля в переменной Max_Height. Каждый раз, когда мы находим поле выше этого Max_Height, мы обновляем Max-Height.so всякий раз, когда мы находим ящик короче, чем Max_Height мы добавляем (Max_Height - высота ящика) к нашему результату. в конце мы вычислили площадь всех предыдущих и следующих скважин. поэтому нам просто нужно вычислить расстояние между первым следующим более высоким ящиком и первое предыдущее более высокое поле и добавляем его к нашему результату. Вот и все.

person user3070752    schedule 13.11.2014