2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 поиск по массиву
Сообщение13.01.2020, 11:10 
Вопрос: есть массив натуральных чисел. Представим себе, что на плоскости он задает некоторую криволинейную трапецию. В этом массиве надо найти прямоугольник максимальной площади, вписанный в эту "трапецию". Двойной цикл не подходит: надо быстрее.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 11:18 
Аватара пользователя
Не совсем понятно условие. Массив пар натуральных чисел? Они заполняют эту "трапецию" или определяют его границу? Ориентация "трапеции" произвольная? Исходный массив как-то упорядочен?

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 15:12 
photon в сообщении #1434847 писал(а):
Не совсем понятно условие. Массив пар натуральных чисел? Они заполняют эту "трапецию" или определяют его границу? Ориентация "трапеции" произвольная? Исходный массив как-то упорядочен?


Уточняю. Задан обыкновенный одномерный неупорядоченный статический массив. Значения в ячейках определяют значения функции одной переменной величины - индекса массива. Ось абсцисс и функция, таким образом определенная, ограничивают криволинейную трапецию на отрезке от единицы до последнего индекса массива. И в эту трапецию надо вписать прямоугольник, то есть найти два индекса массива, таких что произведение модуля их разности на минимальное значение элемента массива в интервале между этими индексами было бы максимальным среди всех возможных пар индексов.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 16:19 
Напрашивается идти одновременно с обоих концов и что-то там запоминать о лучшем прямоугольнике, и сдвигаться в сторону центра то с одной, то с другой стороны в зависимости от того, где будет лучше дельта площади. Доказывать корректность придётся, конечно, чтобы убедиться, что оно работает всегда, а то вдруг нет. ← UPD: это совсем не про криволинейную.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 16:31 
arseniiv в сообщении #1434940 писал(а):
сдвигаться в сторону центра то с одной, то с другой стороны

А вдруг в центре сталактит, упирающийся в пол?
Кстати, всё, что ниже него, входит во все возможные прямоугольники. Это даёт идею решения: выбираем самый низкий("длинный") сталактит, поднимаем дно до него, вся пещера разбивается на две, их рассматриваем по отдельности таким же образом.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 16:34 
А, mea culpa, я пропустил «криволинейную трапецию» в условии. Подумал: о как хорошо, просто трапеция. :facepalm: Зачёркиваю.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 17:09 
Преобразуем массив в двумерный список (значение, индекс), при чем создаем две копии списка. В первой копии списка будут храниться потенциальные координаты левой верхней точки прямоугольника, во второй копии - верхней правой точки прямоугольника. Далее бегаем по спискам и отбрасываем заведомо негодные координаты. Тут уже можно ухищряться. Самое простое, что можно придумать: сравниваем попарно две соседние точки и отбрасываем менее выгодную, при необходимости копируем меньшее значение.
После первого прохода списки похудеют вдвое.
Можно придумать, что делать дальше... Самое простое - перебор влоб.

Еще предложение - сделать списки не двумерные, а трехмерные. Третье значение - обнаруженная прямоугольная площадь слева/справа.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 17:16 
Аватара пользователя
Была такая задача https://www.hackerrank.com/interview/interview-preparation-kit/stacks-queues/challenges - задача "Largest Rectangle". Там придется залогиниться, чтобы посмотреть раздел Editorial, в котором разобрано решение. Не заглядывал, но насколько я знаю, решается при помощи стека за линейное время (идем по массиву и пока значения растут - пушим в стек, когда уменьшаются - вынимаем и считаем площадь).

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 17:21 
Когда координата растёт, это "открывает" новые возможные прямоугольники. Когда координата падает, это "закрывает" возможные прямоугольники. Организуем стек, глубина которого не превышает длину массива. Проходим по массиву один раз. При увеличении текущей координаты добавляем в стек координату левого верхнего угла кандидата. При повторении не делаем ничего. При уменьшении извлекаем левые углы всех закрытых прямоугольников, оставляя один глобально лучший, и, возможно, помещаем в стек один новый левый угол-кандидат.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 17:25 
Аватара пользователя
Сканируйте трапецию горизонтальной линией.

А, это решение $\mathcal{O}(n\log n),$ а тут придумали лучше.

 
 
 
 Re: поиск по массиву
Сообщение13.01.2020, 18:16 
realeugene в сообщении #1434971 писал(а):
Когда координата растёт, это "открывает" новые возможные прямоугольники. Когда координата падает, это "закрывает" возможные прямоугольники. Организуем стек, глубина которого не превышает длину массива. Проходим по массиву один раз. При увеличении текущей координаты добавляем в стек координату левого верхнего угла кандидата. При повторении не делаем ничего. При уменьшении извлекаем левые углы всех закрытых прямоугольников, оставляя один глобально лучший, и, возможно, помещаем в стек один новый левый угол-кандидат.


Спасибо!

 
 
 
 Re: поиск по массиву
Сообщение14.01.2020, 04:17 
Ссылка на разбор (наверное) этой задачи с примером кота, который проходит все тесты на 2 сайтах

 
 
 
 Re: поиск по массиву
Сообщение14.01.2020, 08:32 

(OMG)

_Ivana в сообщении #1435081 писал(а):
Ссылка на разбор (наверное) этой задачи с примером кота, который проходит все тесты на 2 сайтах
if (hln > hrn) нужно было, тоже, в одну строчку написать. Для сохранения стиля породы кота.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group