Блог пользователя mrjackson

Нужна помощь по решению задачи
Автор mrjackson, история, 9 лет назад, По-русски

Пытаюсь решить задачу (http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=111790#1)...Пока безуспешно Как ее решить?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

клик

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо...Можете объяснить идею?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Сортируешь все значения, потом для каждого не использованного бинпоиском ищешь людей с шагом большим D. Так, например, для первого сэмпла возьмем студента, находящегося на позиции 1, от него на расстоянии >= D + 1 находится студент в позиции 11, тогда даем ему тот же вариант и повторяем действие от него.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Будем действовать жадно, отсортируем всех студентов по позиции на оси X.

Допустим мы рассматриваем i-го студента и знаем оптимальный ответ для i-1 его предшественников. Можно проверить подходит ли нам один из этих билетов, если подходит -- отлично берем его, если нет, то добавляем новый билет.

Асимптотика: O(N ^ 2).

Код: link.

P.S. Не сложно довести асимптотику до O(N log(N)) путем добавления структуры данных умеющей находить минимум(например set).

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Наверное меня не одного волнует вопрос, зачем создавать новую учетную запись для создания такого поста?

Вы кого-то боитесь?)

→ Ответить