SJTU 합병 과일

[문제 설명]
지금 은 N 더미 의 과일 이 있 으 니 그들 을 한 무더기 로 합 쳐 야 한다.매번 합병 할 때마다 그 중의 두 무더기 만 합병 할 수 있 습 니 다. 만약 에 합병 하려 는 두 무더기 의 과일 이 각각 a 개의 과일 과 b 개의 과일 이 있다 면 이 두 더 미 를 합병 하려 면 a + b 의 체력 을 소모 해 야 합 니 다.모든 열 매 를 합 친 데 필요 한 최소 체력 수 는 얼마 인지 물 었 다.【 입력 형식 】
모두 두 줄 이다.
첫 번 째 행 위 는 정수 N < = 1000 입 니 다.열매 가 모두 몇 더미 인지 나타 낸다.
두 번 째 줄 은 모두 N 개의 정수 이 고 ai 는 i 번 째 과일 더미 의 수 를 나타 낸다.[출력 형식]
하나의 정수 로 소모 하 는 최소 체력 수 를 나타 낸다.[샘플 입력]
5 1 2 3 4 5
[샘플 출력]
33
[예시 설명]
1, 2 를 합 쳐 체력 3 을 소모 하면 3 크기 의 과일 더미 가 생 긴 다.
체력 9 를 4, 5 로 합치 면 9 크기 의 과일 더미 가 생 긴 다.
3, 3 을 합 쳐 체력 6 을 소모 하면 6 크기 의 과일 더미 가 생 긴 다.
6, 9 를 합 쳐 체력 15 를 소모 하면 15 크기 의 과일 더미 가 생 긴 다.
모두 체력 33 을 소모 합 니 다.
우선 순위 대기 열 헤더 파일

#pragma once

template < class T>
class priorityQueue {
public:
	priorityQueue(int capacity = 100); 
	priorityQueue(const T data[], int size);
	~priorityQueue(); 
	bool isEmpty() const;
	void enQueue(const T & x); 
	T deQueue(); 
	T getHead() const; 
	int size() const { return currentSize; }
	int findMin(T x) {     //       x     
		T Min; 
		int ID = -1;
		for(int i = 1; i <= currentSize; ++i)
			if (array[i] >= x && (Min == -1 || array[i] < Min)) {
				Min = array[i];
				ID = i;
			}
	return ID; 
	}
	void decreaseKey(int i, T value) {  //     i       value
	T x;
	int hole;
	array[hole = i] -= value;      //   i     value
	for(x = array[i]; hole>1 && x < array[hole/2]; hole /= 2)//  
		array[hole] = array[hole / 2];
	array[hole] = x;
	}
private:
	int currentSize;
	T *array;
    int maxSize;
	void doubleSpace() ;
	void buildHeap() ;
	void percolateDown(int hole); //    
};

template < class T>
priorityQueue<T>::priorityQueue(int capacity)
{
	array = new T[capacity];
	maxSize = capacity;
	currentSize = 0;
}

template < class T>
priorityQueue<T>::priorityQueue(const T* items, int size) :maxSize(size + 10), currentSize(size)
{
	array = new T[maxSize];
	for (int i = 0; i <= currentSize; ++i)
		array[i] = items[i];
	buildHeap();
}

template < class T>
priorityQueue<T>::~priorityQueue()
{
	delete[]array;
}

template < class T>
bool priorityQueue<T>::isEmpty()const
{
	return currentSize == 0;
}

template < class T>
T priorityQueue<T>::getHead()const
{
	return array[1];
}

template < class T>
void priorityQueue<T>::enQueue(const T& x)
{
	if (currentSize == maxSize - 1) doubleSpace();
	int hole = ++currentSize;
	for (; hole > 1 && x < array[hole / 2]; hole /= 2)
		array[hole] = array[hole / 2];
	array[hole] = x;
}

template < class T>
void priorityQueue<T>::doubleSpace()
{
	T* tmp = array;
	maxSize *= 2;
	array = new T[maxSize];
	for (int i = 0; i <= currentSize; ++i)
		array[i] = tmp[i];
	delete[]tmp;
}

template < class T>
T priorityQueue<T>::deQueue()
{
	T minItem;
	minItem = array[1];
	array[1] = array[currentSize--];
	percolateDown(1);
	return minItem;
}

template < class T>
void priorityQueue<T>::percolateDown(int hole)
{
	int child;
	T tmp = array[hole];
	for (; hole * 2 <= currentSize; hole = child)
	{
		child = hole * 2;
		if (child != currentSize && array[child + 1] < array[child])
			child++;
		if (array[child] < tmp) array[hole] = array[child];
		else break;
	}
	array[hole] = tmp;
}

template < class T>
void priorityQueue<T>::buildHeap()
{
	for (int i = currentSize / 2; i > 0; i--)
		percolateDown(i);
}

cpp 파일:

#include 
#include "priorityQueue.h"
using namespace std;

int main()
{
	int n, num;
	priorityQueue<int> q;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		q.enQueue(num);
	}
	int ans = 0, a, b;
	while (q.size() > 1)
	{
		a = q.deQueue();
		b = q.deQueue();
		ans += a + b;
		q.enQueue(a + b);
	}
	cout << ans << endl;
	return 0;
}

토로: 이 문 제 는 숙제 문제 입 니 다. 수업 진도 가 아직 우선 순위 대열 에 이 르 지 않 았 기 때문에 선생님 이 기대 하 는 방법 은 우선 순위 대열 로 하프 만 을 실현 하 는 것 이 아 닐 것 입 니 다.하지만...................................................................