PROBLEM LINK:
Author: mehul_dholiya
Editorialist: mehul_dholiya
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Heaps, Priority Queue
PROBLEM:
We are given an array of N elements and a number K. In each of the K moves, we need to select the array element with maximum value and decrease its value by 1 until it becomes 0.
EXPLANATION:
The first thing to note is that K can range up to 10^6, so we have to find array element with maximum value for each iteration in complexity less than or equal to O(log n).
This suggests use of priority queue as we can achieve this task using priority queue in complexity of O(log n).
The question says that in case of two array elements with same value, we have to select the one with minimum index. This gives us how to order our elements in priority queue.
So, our priority queue will consist of pairs (a,b), a being the array element and b being its index. The priority queue will be ordered in decreasing order by a and increasing order by b.
We will first insert all pairs (value,index) in priority queue. The priority queue will be ordered as described above. Then in each of the K queries, we will pop the first element in the priority queue and print its index and insert the pair (value-1,index) in the priority queue.