Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Подскажите алгоритм
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Даны координаты левого верхнего и правого нижнего угла прямоугольного окна (координаты - целые числа, меньше 10^5 по модулю), их количество <=50000. Нужно найти точку, которая покрыта наибольшим числом окон, вывести искомое количество окон и координаты точки.
Я когда-то встречал такую задачу. Тогда мне в голову пришла идея использовать СНМ(Система непересекающ. множеств). Хотя тогда я не смог реализовать.
Очевидно, что данную точку следует искать на границе прямоугольника, причем ее икс координата будет совпадать с икс координатой левой или правой стороны одного из прямоугольников, а так же игрек координата будет совпадать с игрек координатой нижней или верхней стороны одного из прямоугольников (не обязательно того же самого).
Отсортируем все икс координаты по возрастанию и сделаем заметание вертикальной прямой. Заведем дерево отрезков по игрек координатам, которые встречались среди игрек координат прямоугольников. Когда мы встречаем левую границу прямоугольника, увеличиваем в дереве отрезков значения на отрезке от нижнего до верхнего игрека на 1. Когда встречаем правую границу - уменьшаем значения. После каждой такой операции смотрим максимум в дереве. Тогда максимум среди всех таких максимумов и будет искомой точкой. Сложность O(NlogN).
Извините, что такое заметание вертикальной прямой?
Сканирующей прямой это ещё называют - т.е. мы проводим вертикальную прямую x = -infty, потом двигаем её слева направо - к x = +infty, по пути просматривая все изменения, которые происходят с картинкой.
Когда мы встречаем левую границу прямоугольника, увеличиваем в дереве отрезков значения на отрезке от нижнего до верхнего игрека на 1.
Можете пояснить, что значит "от нижнего до верхнего игрека". Т.е. мы встретили прямоугольник, смотрим какие у него координаты по игреку и в дереве отрезков увеличиваем значения у тех координат, что входят в данных прямоугольник?
Можно, конечно, и так, но я бы предпочел в начале сжать координаты, оставив только игреки нижних и верхних сторон прямоугольника и строить дерево отрезков уже не по абсолютным координатам, а по номерам в отсортированном массиве игреков. Тогда когда мы встретили прямоугольник можем бинпоиском найти номера его верхнего и нижнего игрека и в дереве отрезков сделать +1 между этими номерами.
У меня наконец-то дошли руки до этой задачи!
Но столкнулся с проблемами (WA) при реализации дерева отрезков в виде:
- за O(logN) на отрезке прибавлять +-1
- за O(logN) возвращать максимум на всём массиве и его номер.
При замене дерева на линейное прибавление TL на больших тестах, т.е. ошибка в дереве отрезков.
Вот функция обновления(t - массив прибавлений, tmax - максимум на подотрезке, wmax - где находится текущий максимум на подотрезке):
void update(int v,int tL,int tR,int l,int r,int add){
if (l>r) return;
if (tR==tL|(tL==l&tR==r)) {t[v]+=add;tmax[v]+=add;return;}
int tM=(tL+tR)/2;
update(v*2,tL,tM,l,min(r,tM),add);
update(v*2+1,tM+1,tR,max(l,tM+1),r,add);
tmax[v]=-99999999;
if (tmax[v]<tmax[v*2+1]) {tmax[v]=tmax[v*2+1]+t[v];wmax[v]=wmax[v*2+1];}
if (tmax[v]<tmax[v*2]) {tmax[v]=tmax[v*2]+t[v];wmax[v]=wmax[v*2];}
}Весь код: http://pastebin.com/JQbFsGCD
UPD:Игнор
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Подскажите алгоритм