Блог

Я готовлюсь к соревнованию ACM, и я застрял с этой проблемой.

У вас есть здания с заданной позицией Xi и высотой Hi щиты сделаны из стали, и их должны поддерживать как минимум два здания одинаковой высоты. Правый конец экрана должен находиться на вершине какого-либо здания. Все здания, которые находятся под экраном (включая те, которые находятся на конце), защищены этим экраном, и их высота не может превышать высоту, на которой размещен экран. Одно здание может быть защищено не более чем одним экраном.

Вам дается бесконечное количество щитов, каждый с одинаковой длиной L. Найдите максимальное количество зданий, которые могут быть защищены щитами, и найдите минимальное количество щитов, которые можно использовать для защиты максимального количества зданий.

Ввод

Первая строка ввода содержит одно положительное целое число T (1 <= T <= 20), количество тестовых примеров.

Каждый тестовый пример начинается со строки, содержащей ровно два целых числа: количество зданий N (2 <= N <= 100 000) и длина щита L (1 <= L <= 1 000 000 000). В каждой из следующих N строк есть два целых числа: Xi (положение i-го здания, 0 <= Xi <= 1,000,000,000) и Hi (высота i-го здания, 1 <= Hi <= 1,000,000,000). Здания отсортированы по их координате x. Не будет двух зданий с одинаковой координатой x.

Вывод

Для каждого тестового примера, по две в строке, выведите максимальное количество зданий, которые могут быть покрыты, и минимальное количество щитов, которые могут быть использованы для этой цели.

Пример

 Input
17 3
1 2
2 1
3 2
4 3
5 1
6 2
7 4
8 2
9 3
10 4
11 2
15 2
16 1
17 3
18 3
19 1
20 2

Output
11 3

Explanation:
first shield: 1,2,3 
second shield: 7,8,9,10
third shield:  15,16,17,18
  

Очевидно, что решение методом грубой силы легко кодируется, но не выполняется по времени (1 сек), я читал о дереве сегментов, но поскольку я не работал с деревом сегментов, мне интересно, это способ решения этой проблемы или есть какое-то более простое решение, которое я упускаю?

P.S Хотя в нем указано, что длина щита равна L, на самом деле это L 1, последнее здание должно быть самым высоким и иметь здание на позиции [Xi-1, Xi-L] с одинаковой высотой, чтобы можно было разместить щит, и позиции зданий будут отсортированы.

Нахождение максимального значения от pos - k до pos также известно как «задача о максимуме скользящего окна», и она имеет простое O(N) решение без деревьев сегментов или каких-либо других сложных структур данных.
Алгоритм следующий:
1) Давайте сохраним a deque пар <value, position> .
2) Перемещение границ окна выполняется следующим образом (здесь я использую псевдокод):

 //Moving the right border.
right <- right   1
cur <- pair<value[right], x[right]>
while not deque.empty and deque.back.value < cur.value
    deque.pop_back()
deque.push_back(cur)

//Moving the left border.
left <- left   1
while deque.front.position is out of [x[left], x[right]] bounds
    deque.pop_front()
  

3) Максимум просто deque.front.value .

Сложность этого алгоритма заключается O(N) в том, что каждый элемент помещается в deque только один раз и удаляется из него только один раз (и каждая итерация while цикла в псевдокоде выше удаляет один элемент из deque).

Теперь решение исходной проблемы о щитах:
1) Предположим dp[pos] , что = pair<максимальное количество охваченных зданий, минимальное количество используемых щитов> так, чтобы правая граница всех щитов была <= pos .
2) Давайте сохраним два указателя low и high . Это high указатель на текущее здание, а low указатель — указатель на крайнее левое здание, такое, что x[high] - x[low] >= L .
3) high указатель всегда увеличивается на единицу в for цикле, и low указатель настраивается соответствующим образом (для удовлетворения свойства 2)).
4) Затем dp может быть вычислено следующим образом: для фиксированного значения high , dp[high] является либо dp[high - 1] или dp[low - 1] high - low 1 (второе используется, только если возможно разместить экран от low до high ).
5) Как проверить, можно ли разместить экран? Используя алгоритм скользящего окна maximum, можно поддерживать максимальное значение в [low; high - 1] диапазоне и проверять, равно ли оно H[high] .
6) Ответ dp[N - 1] (с индексацией на основе 0).

Сложность этого решения заключается O(N) в том, что low и high всегда увеличиваются, и их нельзя увеличивать более N раза, а максимальная сложность алгоритма скользящего окна была показана выше.