Разбор задачи 11D

Итак, сначала решим более простую подзадачу:

Дополнительное ограничение: b[i] >= 0.

Как решать? Отсортируем всех друзей по возрастанию a[i]. Будем брать всех в таком порядке. Как только мы кого-то не сможем взять, у нас не получится взять и всех остальных.

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

Без дополнительного ограничения. Сначала, опять же, возьмем всех друзей с b[i] >= 0, как в первом пункте. После этого мы достигнем максимально возможного авторитета, обозначим его за A.

Остались только друзья, уменьшающие авторитет. Два решения позволяют их выбирать:

• неправильное решение — выбирать в порядке убывания b[i]. Почему? Я придумал контртест (см. ниже). Ты выберешь сначала второго и проиграешь.

2 0
0 -1000
-1000 -1

• авторское решение (источник — командная интернет-олимпиада ИТМО, 19.11.2015, усложненная номинация) решает задачу за n^2 для n <= 1000 методом динамического программирования:
  
  Не сортируем остальных и считаем динамику: a[i][j] — максимальный оставшийся авторитет, если из первых i друзей в списке выбрать ровно j, или –∞, если это невозможно.
  
  Формула для пересчета: dp[i][j] = dp[i-1][j], если dp[i-1][j-1] < a[i], или dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + b[i]), если dp[i-1][j-1] >= a[i].
• существует также жадный алгоритм: сортируем оставшихся друзей по (a[i] + b[i], и выбираем их в порядке убывания этой величины. Наверное, тебе не понятно, почему это так работает? Сейчас я докажу. Рассмотрим последнего выбранного друга i. Тогда для него будет верно, что

• Теперь сделаем математический фокус: прибавим к обоим частям b[i]:

• В правой части получилась сумма всех отрицательных b(j) у выбранных друзей. Соответственно, в оптимальном варианте в правой части какое-то константное выражение, не зависящее от порядка выбора друзей, а только от общего списка друзей.
  А в левой части выражение зависит от последнего выбранного друга.
  Значит, нам будет выгодно (= это будет самым удобным способом удовлетворить неравенство) брать друга с минимальной суммой a[i] + b[i] последним.
• Далее по индукции можно убрать этого друга и доказать, что всех друзей нужно брать в порядке убывания a[i] + b[i], что и требовалось доказать.

Время работы решения — O(n log n), память — O(n).