컴퓨터실

1. 힙 정렬

2. comp 함수

3. 문제 읽고, 예외사항 없이 정리

/* 컴 퓨 터 실*/
#include <stdio.h>
struct data
{
	int gap, start;
}heap[300010];
int a[100010], b[100010];
int last;
int M, N, Q; //컴퓨터의 수 M, 이미 자리를 잡은 학생의 수 N, 친구의 수 Q
int comp(int i, int j)
{
	if (heap[i].gap == heap[j].gap) return heap[j].start - heap[i].start;
	return heap[i].gap - heap[j].gap;

}
void swap(int a, int b)
{
	struct data temp = heap[b];
	heap[b] = heap[a];
	heap[a] = temp;
}
void push(int g, int s)
{
	int c, p;

	heap[++last] = { g, s };
	c = last; p = c / 2;
	while (p > 0)
	{
		if (comp(c, p) > 0)
		{
			swap(c, p);
			c = p; p = c / 2;
		}
		else break;
	}
}
struct data pop(void)
{
	int c, l, r, p;
	struct data rtn = heap[1];
	heap[1] = heap[last--];

	p = 1; l = 2; r = 3;
	while (l <= last)
	{
		if (l == last) c = l;
		else c = comp(l, r) > 0 ? l : r;
		if (comp(c, p) > 0)
		{
			swap(c, p);
			p = c; l = p * 2; r = l + 1;
		}
		else break;
	}
	return rtn;
}
int main(void)
{
	struct data d;
	int e, n;
	int k = 0, cnt;
	scanf("%d %d %d", &M, &N, &Q);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &a[i]);
		push(a[i] - a[i - 1] - 1, a[i - 1] + 1);

	}
	push(M - a[N], a[N] + 1);
	for (int i = 1; i <= Q; i++) scanf("%d", &b[i]);


	for (cnt = 1; cnt <= Q; cnt++)
	{
		if (b[cnt] <= N)printf("%d\n", a[b[cnt]]);
		else break;
	}

	for (int i = N + 1; i <= b[Q]; i++)
	{
		d = pop();
		e = d.start + d.gap - 1;
		n = (d.start + e) / 2;
		if (n > d.start)push(n - d.start, d.start);
		if (e > n)push(e - n, n + 1);
		if (b[cnt] == i)
		{
			printf("%d\n", n);
			cnt++;
		}

	}
	return 0;
}