проблем
Вътре има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).
Код
Java
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) за приоритетна опашка
Това е всичко !
