Проблема
В них N мешочков с бриллиантами. i-й из этих мешков содержит A[i]алмазов. Если вы уроните сумку с алмазами A[i], она изменится на A[i]/2алмазов, а вы получите A[i]. бриллианты. Сбрасывание сумки занимает 1 минуту. Найдите максимальное количество алмазов, которое вы можете получить, если вам дается K минут.
Пример 1:
Input:
N = 5, K = 3
A[] = {2, 1, 7, 4, 2}
Output:
14
Explanation:
The state of bags is:
2 1 7 4 2
You take all diamonds from Third bag (7).
The state of bags becomes: 2 1 3 4 2
Take all diamonds from Fourth bag (4).
The state of bags becomes: 2 1 3 2 2
Take all diamonds from Third bag (3).
The state of bags becomes: 2 1 1 2 2
Hence, number of Diamonds = 7+4+3 = 14.
Подход
Мы должны бросать K раз, и каждый раз это будет половина счета.
Поскольку нам нужно максимизировать результат, мы выберем K самых высоких бриллиантов.
Ex: [2, 1, 7, 4, 2]
Итак, мы можем выбрать 7, теперь это [2, 1, 3, 4, 2]
теперь мы можем выбрать 4, теперь это [2, 1, 3, 2, 2]
теперь мы можем выбрать 3, теперь это [2, 1, 1, 2, 2]
так что в 3 раза всего будет 7 + 4 + 3 = 14.
Итак, нам нужна структура данных, чтобы она могла вставлять новую запись сверху, и мы могли получить верхний элемент.
Итак, мы знаем, что здесь PriorityQueue может быть лучшим вариантом, поскольку он может вставлять новый элемент за O(logN) и удалять верхний элемент за O(logN).
Код
Джава
class Solution {
static long maxDiamonds(int[] A, int N, int K) {
// code here
long result = 0l;
PriorityQueue<Integer> pq = new PriorityQueue<>((p1, p2) -> p2-p1);
for(int x: A) pq.add(x);
while(K-- > 0) {
int poll = pq.poll();
result += (long)(poll);
pq.add(poll/2);
}
return result;
}
};
Сложность времени
O(NlogN)
Вставка всех элементов в приоритетную очередь займет O(NlogN).
Тогда для извлечения K элементов потребуется O(KlogN).
Снова вставка этих элементов K займет O (KlogN).
Итого => O(NlogN) + O(KlogN) + O(KlogN) => O(NlogN)
Космическая сложность
O(N) для приоритетной очереди
Вот и все !
