Задача с использованием алгоритмов сортировки

Рейтинг: 2Ответов: 1Опубликовано: 04.10.2014

Цитирую полный текст задачи:

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.

Формат входного файла

Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.

Формат выходного файла

Выведите M чисел – толщину носкового покрытия в каждой точке.

На первый взгляд, задача кажется весьма простой. Но, используя те поверхностные идеи для ее решения, она часто не проходит по времени (1 секунда). Собственно, был бы очень рад послушать ваши идеи алгоритмов для ее решения.

P.S. Авторы дают небольшую подсказку: использовать сортировку.

алгоритм сортировка
Источник: Stack Overflow на русском

Ответы

▲ 1

Интереса некорыстного ради сделал на JS. При максимальных параметрах считает меньше секунды на стареньком макбуке.

  1. старый вариант;
  2. новый целочисленный вариант.

Алгоритм для целочисленных координат:

  1. адреса 1..10000 это всего 14 бит. Сдвигаем их на 3 влево. А 3 новых младших бита будут обозначать тип "события":
    • 001 — начало;
    • 010 — конец;
    • 100 — контрольная точка (КТ).
  2. создаём один массив чисел bin, где будут и события начала/конца (Н/К), и КТ
  3. копируем в него события Н/К в новом виде
  4. копируем в него КТ в новом виде
  5. сортируем как числа по возрастанию
  6. двигаясь от начала меняем счётчик в зависимости от встреченных событий для Н/К (биты 0 или 1 установлены)

  7. по достижении контрольных точек (бит 2 установлен) снимаем текущее показание счётчика.

    Отрезки считаю как [..) — начало входит, конец не участвует.

Старый алгоритм:

  1. координаты концов носков умножить на -1 — так удобнее в данной постановке задачи, где координаты начал всегда положительны;
  2. отсортировать «события» по возрастанию абсолютного значения (игнорируя знаки);
  3. контрольные точки тоже отсортировать по возрастанию;
  4. инициализируем в 0 текущее значение суммы (С): к ней будет +1 или -1, в зависимости от знака очередного начала/конца носка;
  5. два «курсора» указателя - на текущее «событие» носков (может, начало, может, конец), и текущую ожидаемую контрольную точку (К.Т.);
  6. делаем шаг в носках. Смотрим, не перешагнули ли уже одну или несколько К.Т.;
  7. если перешагнули - эти К.Т. получают текущее значение суммы, и курсор К.Т. сдвигается дальше;
  8. обновляем сумму С на текущее "событие" (+- 1);
  9. следующий шаг в носках (go to 6).

Upd. в Хроме отсутствует ф-я Math.sign(). Обновил ссылку, работает в Chrome.

Upd. 2. невежественно пропустил краевые эффекты. Теперь учёл начала/концы интервалов согласно практике [...) — начало отрезка входит в измерение, конец — нет. И добавил график для наглядности.

график