UPD: сдалось, доказательство dalex
Не могу решить задачу 788. Интересная игра с числами с сайта acmp.ru. Жадное решение (отсортировать пары по (a, b) и по (b, a) в двух массивах, идти по ним двумя указателями и набирать для каждого игрока из начала массивов еще никем не взятые пары) — не проходит, на этом идеи закончились. Подкиньте, пожалуйста, идеи, или направьте рассуждения в правильном направлении, может на codeforces есть аналогичная задача с разбором, заранее спасибо.
Лень думать, какая из этих идей правильная(обе попробуй):
-Отсортируй пары по убыванию a + b, игроки идут с начала
-Отсортируй пары по a - b, игроки идут с разных концов
Первое сдалось, неужели большой опыт решения задач сходу позволяет находить правильные идеи для жадного алгоритма, не доказывая их?
Я так рассуждал: очевидно, что надо сортировать пары, и надо понять, как сортировать. Пусть мы сравниваем пары i и j, тогда первому игроку лучше брать i, если ia - jb > ja - ib, то есть если ia + ib > ja + jb, и второму лучше брать i, если ib - ja > jb - ia→ia + ib > ja + jb, ну и дальше понятно, что надо сортить по сумме. Вторая идея родилась из-за путаницы со знаками в оперативной памяти моего мозга.
Ой-ой-ой, какая хорошая задача!
Немного видоизменим задачу: пусть второй игрок забрал себе все элементы, и теперь в нечетные ходы первый игрок будет отбирать у него элементы себе, а в четные второй игрок будет защищать один из своих элементов от взятия первым игроком.
Тогда у первого в начале игры 0, а у второго sum(b[i]). И каждым ходом, если первый игрок отобрал j-ый элемент, он получает a[j] очков, а второй теряет b[j] очков. Это равносильно тому, что первый получает a[j]+b[j], а второй ничего не теряет.
Сортим по a[i]+b[i] и отдаем первому игроку каждый нечетный (в 1-индексации) элемент.
Красиво, спасибо!
Есть еще одна задача на жадный алгоритм на acmp.ru, которую я сдал без доказательства, 806. Белоснежка и n гномов. Наверное, эта задача связана с ней, или даже аналогична, так как в принятом решении — сортировка по a[i] + b[i] и проверка за линию на то, что у Белоснежки есть свободная минута.
Держи еще в некоторой степени похожие задачи:
100488K - Два пирата
101149B - Не время для драконов