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

Задачка про лжецов :)
Автор vsb, 14 лет назад, По-русски
Всем привет!

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

Есть N человек расположенных на оси OX. Каждый из них сказал, сколько человек строго справа от него и сколько строго слева -- right[i], left[i] (в одной точке может находиться несколько человек). Требуется подсчитать сколько максимум человек говорят правду.

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сортируем по возрастанию left, затем динамика, которая возвращает количество правдивых для первых k человек, если k-ый говорит правду. Как то так...
→ Ответить
14 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Несколько человек могут находиться в одной точке?
А, извиняюсь, недочитал пост до конца...
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Эта задача была на одном из раундов про грузовики и монстра ДравДэ. 

http://codeforces.ru/blog/entry/678 - разбор

http://codeforces.me/contest/28/problem/D - задача

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

    Только это другая задача - там не могло быть нескольких грузовиков в одной точке..

    А эта больше похожа на задачу про черепашек с NEERC 2004 (J).

    И решается она как-то так:

    Строим граф из N + 1 вершины.

    Для каждой пары вершин (i, j), где i < j, проводим ребро из i-ой вершины в j-ую весом max(j - i - k, 0), где k - количество человек, которые сказали, что слева от них стоит i человек, а справа - (N - j).

    И ищем чем-нибудь кратчайший путь между вершинами 0 и N.

    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, это именно эта задача.
      Большое спасибо за красивое решение. Я сначала долго не мог понять, откуда оно берется, но потом разобрался и хочу описать здесь своими словами, может пригодится..:

      Найдем минимальное количество человек, которые врут.
      Построим граф из N + 1 вершины. И нам надо пройти по этому графу из вершины 0 в вершину N. переходя из i в j надо посчитать сколько человек будут врать, если все люди c i-го по (j - 1)-го будут расположены в одной точке. Это можно посчитать по формуле которую привел Дмитрий Жуков. В ней мы считаем количество человек, которые не сказали правду, чтобы ребро (i, j) стало "правдивым". Получится, что стоимость пути равна количеству врунов. Теперь осталось среди всех возможных путей найти такой, где меньше всего людей соврало, это и будет минимальный по стоимости путь.

      → Ответить
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Какие на N ограничения?

→ Ответить