Добрый день, на acmp.ru есть такая задача: Подарки

Я пытался решить таким образом:

Если входные данные:

5 10
4 7 4 3 10

Сначало сортировал массив по неубыванию,

3 4 4 7 10

А далее делал так:

while(M > 0)
	{
		int t = A[1] - A[0];
		if(M > t)
		{
			M -= (t + 1);
			A[0] += (t + 1);
		}
		else
		{
			A[0] += M;
			M = 0;
		}
		
		i = 0;
		while(A[i] > A[i + 1] && i < N - 1)
			swap(A[i], A[i + 1]), i++;
	}

А — отсортированный массив

N — кол. элементов массива

M — кол. конфет

Надеюсь по алгоритму, идея решения ясна.. В конце работы алгоритма первый элемент массива и будет ответом.

Но такое решени не эффективное на больших входных данных и получаю TL на 10 тесте.

Теперь хочу попробовать решить через двоичные деревья, т.к. это у меня работает за O(N)

while(A[i] > A[i + 1] && i < N - 1)
			swap(A[i], A[i + 1]), i++;

А если сделать через min heap, то будет за O(log N).

У меня возникло 2 вопроса:

1) Как можно реализовать этот min heap самому, что бы там были методы добавления, и удаления корневого элемента? Если у кого есть пример, буду благодарен. В сети не нашел хороших примеров, а сам реализовал совсем не правильно.

2) Как тоже самое сделать через priority_queue? Проблема в том, что по умолчанию этот контейнер в С++ в корневом элементе хранит максимальный элемент, т.е. max heap. А мне нужно наоборот.

Я в справочнике читал, что там ему можно параметр передавать компатор(не знаю как правильно называется). В сети нашел несколько примеров, только там этот "компатор" был классом у которого много разных методов и перегруженных операторов. Тупо copy/paste не стал делать, хотел бы разобраться что и зачем.

Если кто знает, подкажите пожалуйста как сделать так, что бы в этом контейнере сортировка была по неубыванию.

Буду благодарен.