boj 11000번. 강의실 배정.

 

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제는 최소힙을 통해 정렬된 값을 기준으로 하나씩집어넣다가 

저장된 값보다 s가 크다면 팝하고 로테이트를 반복해주는 로직을 통해서 

구현할 수 있다.

 

관련된 코드를 첨부하겠다.

class Heap {
public:
	Heap() : len(0) {}
	void add(int s, int e);
	void pop();
	int top();
	void childSwap();
	void parentSwap();
public :
	vector<int> v;
	int			len;
};

void Heap::add(int s, int e) {
	if (len >= 1 && this->top() <= s) {
		this->childSwap();
	}
	v.push_back(e);
	++len;
	this->parentSwap();
}

int Heap::top() {
	if (len == 0)
		return (-1);
	return (this->v[0]);
}

void Heap::pop() {
	v.pop_back();
	--len;
}

void Heap::parentSwap() {
	int i;
	int s = len - 1;
	i = (s - 1) / 2;
	for (; i >= 0; i = (i - 1) / 2) {
		if (v[i] > v[s]) 
			swap(v[i], v[s]);
		if (i == 0)
			break ;
		s = i;
	}
}

void Heap::childSwap() {
	if (len < 1)
		return ;
	v[0] = v[len - 1];
	this->pop();
	int i, s;
	s = 0;
	for (i = 1; i < len;) {
		if (i + 1 < len && v[i + 1] < v[i])
			++i;
		if (v[i] < v[s])
			swap(v[i], v[s]);
		else
			break;
		s = i;
		i = i * 2 + 1;
	}		
}