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

Автор dmkz, история, 6 лет назад, По-русски

UPD: сдалось, доказательство dalex

Не могу решить задачу 788. Интересная игра с числами с сайта acmp.ru. Жадное решение (отсортировать пары по (a, b) и по (b, a) в двух массивах, идти по ним двумя указателями и набирать для каждого игрока из начала массивов еще никем не взятые пары) — не проходит, на этом идеи закончились. Подкиньте, пожалуйста, идеи, или направьте рассуждения в правильном направлении, может на codeforces есть аналогичная задача с разбором, заранее спасибо.

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

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

Лень думать, какая из этих идей правильная(обе попробуй):
-Отсортируй пары по убыванию a + b, игроки идут с начала
-Отсортируй пары по a - b, игроки идут с разных концов

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

    Первое сдалось, неужели большой опыт решения задач сходу позволяет находить правильные идеи для жадного алгоритма, не доказывая их?

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

      Я так рассуждал: очевидно, что надо сортировать пары, и надо понять, как сортировать. Пусть мы сравниваем пары i и j, тогда первому игроку лучше брать i, если ia - jb > ja - ib, то есть если ia + ib > ja + jb, и второму лучше брать i, если ib - ja > jb - iaia + ib > ja + jb, ну и дальше понятно, что надо сортить по сумме. Вторая идея родилась из-за путаницы со знаками в оперативной памяти моего мозга.

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

Ой-ой-ой, какая хорошая задача!

Решение