6.3. Задача «Рекламная кампания»

Представим, что вы владелец популярной страницы в интернете, на которой есть рекламных мест. Вы хотите продать их рекламодателям, которые рассчитывают на , и кликов в день и при этом готовы платить , и за клик. Как подобрать пары рекламных мест и рекламодателей так, чтобы получить максимальную прибыль? Например, доход от отмеченных голубым цветом пар, приведённых выше, составит долларов; от отмеченных чёрным — .

• Входные данные: В первой строке приведено целое число , во второй — последовательность целых чисел , в третьей — последовательность целых чисел .
• Выходные данные: Максимальное значение , где — это перестановка .
• Ограничения: ; для всех .

Пример 1Пример 1

Ввод	Вывод
1 23 39	897

.

Пример 2Пример 2

Ввод	Вывод
3 2 3 9 7 4 2	79

.

РешениеРешение

Суть решения заключается в том, чтобы отдать самое популярное рекламное место самому дорогому объявлению. Вас вряд ли удивит, что жадный подход даст максимальную прибыль.

Предположим, что и — самые большие элементы: и для всех . Мы утверждаем, что существует оптимальное решение, объединяющее с .

Чтобы доказать это, возьмём оптимальное решение и предположим, что в нём объединены и для и и для . Покажем, что замена пар и на пары и только повысит прибыль.

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

После замены:

Таким образом, замена увеличивает общую прибыль на

Это приводит нас к алгоритму, который объединяет рекламное объявление с максимальным количеством кликов за максимальную цену, исключает их из вариантов на рассмотрение и повторяет то же самое.

Revenue(Click,Price):
     revenue = 0
     while clicks is not empty:
        p = index with largest Click[p]
        q = index with largest Price[q]
        revenue = revenue+Clicks[p]⋅Price[q]
        remove p-th element of Click
        remove q-th element of Price
     return revenue

Время выполнения.
Время выполнения этого алгоритма — . В каждой из итераций мы проводим линейное сканирование и находим два самых больших элемента. Также можно отсортировать эти два списка заранее, чтобы не искать самый большой элемент с нуля при каждой итерации. Это приводит нас к решению с временем выполнения .