Представим, что вы владелец популярной страницы в интернете, на которой есть $n=3$ рекламных мест. Вы хотите продать их рекламодателям, которые рассчитывают на $clicks_1=10$, $clicks_2=20$ и $clicks_3=30$ кликов в день и при этом готовы платить $price_1=2$, $price_2=3$ и $price_3=5$ за клик. Как подобрать пары рекламных мест и рекламодателей так, чтобы получить максимальную прибыль? Например, доход от отмеченных голубым цветом пар, приведённых выше, составит $10 \cdot 5 + 20 \cdot 2 + 30 \cdot 3 = 180$ долларов; от отмеченных чёрным — $10\cdot 3 + 20 \cdot 5 + 30 \cdot 2=190$.
- Входные данные: В первой строке приведено целое число $n$, во второй — последовательность целых чисел $price_1, \dotsc, price_n$, в третьей — последовательность целых чисел $clicks_1, \dotsc, clicks_n$.
- Выходные данные: Максимальное значение $(price_1 \cdot c_1 + \dotsm + price_n \cdot c_n)$, где $c_1, \dotsc, c_n$ — это перестановка $clicks_1, \dotsc, clicks_n$.
- Ограничения: $1 \le n \le 10^3$; $0 \le price_i,clicks_i \le 10^5$ для всех $1 \le i \le n$.
Пример 1
Ввод | Вывод |
---|---|
2 23 39 | 897 |
$897=23 \cdot 39$.
Пример 2
Ввод | Вывод |
---|---|
3 2 3 9 7 4 2 | 79 |
$79=7 \cdot 9 + 2 \cdot 2 + 3 \cdot 4$.
Решение
Суть решения заключается в том, чтобы отдать самое популярное рекламное место самому дорогому объявлению. Вас вряд ли удивит, что жадный подход даст максимальную прибыль.
Предположим, что $clicks_p$ и $price_q$ — самые большие элементы: $clicks_p \ge clicks_i$ и $price_q \ge price_i$ для всех $i=1,\dotsc,n$. Мы утверждаем, что существует оптимальное решение, объединяющее $clicks_p$ с $price_q$.
Чтобы доказать это, возьмём оптимальное решение и предположим, что в нём объединены $clicks_p$ и $price_{q'}$ для $q' \neq q$ и $price_q$ и $clicks_{p'}$ для $p' \neq p$. Покажем, что замена пар $(p,q')$ и $(p',q)$ на пары $(p,q)$ и $(p',q')$ только повысит прибыль.
Давайте оценим, как такая замена повлияет на общую прибыль.
До замены рассматриваемые элементы давали следующую прибыль:
$$
clicks_p\cdot price_{q'}+clicks_{p'}\cdot price_{q}
$$
После замены:
$$
clicks_{p}\cdot price_{q}+clicks_{p'}\cdot price_{q'}
$$
Таким образом, замена увеличивает общую прибыль на
$$ clicks_{p} \cdot price_{q}+clicks_{p'}\cdot price_{q'} - clicks_p\cdot price_{q'}-clicks_{p'}\cdot price_{q}=(clicks_{p}-clicks_{p'})\cdot(clicks_{q}-clicks_{q'}) \ge 0 $$
Это приводит нас к алгоритму, который объединяет рекламное объявление с максимальным количеством кликов за максимальную цену, исключает их из вариантов на рассмотрение и повторяет то же самое.
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
Время выполнения. Время выполнения этого алгоритма — $O(n^2)$. В каждой из $n$ итераций мы проводим линейное сканирование и находим два самых больших элемента. Также можно отсортировать эти два списка заранее, чтобы не искать самый большой элемент с нуля при каждой итерации. Это приводит нас к решению с временем выполнения $O(n\log n)$.