5. 10755 컴퓨터실

원본 출처 : https://www.acmicpc.net/problem/10755

10755번: 컴퓨터실

문제 풀이 : 

// 힙 자료구조 활용 - 컴퓨터
 
#include <stdio.h>
#define MAX 300000
int M, N, Q;
int A[MAX + 1]; // 기존학생과 마지막 친구의 순번까지의 앉은 컴퓨터 자리 기록
int B[1000001]; // Q명의 친구들의 순번
int tmp[MAX + 1];   //merge_sort에 사용될 임시 배열
void merge_sort(int s, int e) {
    if (s >= e) return;
    int m = (s + e) / 2;
    //분할
    merge_sort(s, m);
    merge_sort(m + 1, e);
    //정복
    int l_p = s, r_p = m + 1, t_p = s;
    while (l_p <= m && r_p <= e) {
        //비교
        if (A[l_p] < A[r_p]) {
            tmp[t_p++] = A[l_p++];
        }
        else {
            tmp[t_p++] = A[r_p++];
        }
    }
    //남은 것들
    while (l_p <= m) {
        tmp[t_p++] = A[l_p++];
    }
    while (r_p <= e) {
        tmp[t_p++] = A[r_p++];
    }
    //tmp배열을 원 배열로 복사
    for (t_p = s; t_p <= e; t_p++) {
        A[t_p] = tmp[t_p];
    }
}
 
typedef struct {
    int s, e, cnt;
}NODE;
 
NODE heap[MAX + 1]; // 0번 방 사용 하지 않는 것 고려
int last = 0;
 
int comp(int x, int y) { // x : 부모(왼쪽), y : 자식(오른쪽)
    if (heap[x].cnt > heap[y].cnt) return 1;
    else if (heap[x].cnt == heap[y].cnt && heap[x].s < heap[y].s) return 1;
    else return 0;
}
 
 
int push(int s, int e, int cnt) {
    int p, c;
    NODE temp;
    if (last == MAX) return 0; //full 조건
    last++;
    heap[last].s = s;
    heap[last].e = e;
    heap[last].cnt = cnt;
 
    c = last; p = c / 2; // 부모와 자식의 위치 정함
    while (p > 0) { // 부모가 최상위 노드까지 경쟁시켜야함
        if (comp(c, p) == 1) {
            temp = heap[p];
            heap[p] = heap[c];
            heap[c] = temp;
            c = p; p = c / 2;
        }
        else break;
    }
    return 1;
}
 
int pop(NODE *d) {
    int p, l, r, c;
    NODE  temp;
    if (last == 0) return 0; // empty 조건
    *d = heap[1]; // 최상위 노드 전달
    heap[1] = heap[last]; // 마지막 노드를 최상위노드로 배치
    last--;
    p = 1; l = 2 * p; r = l + 1;
    while (l <= last) {
        if (l == last) c = l; // 자식이 1명인 경우
        else if (comp(l, r) == 1) c = l; // 자식이 2명인 경우, 더큰 값을 후보자로
        else c = r;
        if (comp(c, p) == 1) {
            temp = heap[p];
            heap[p] = heap[c];
            heap[c] = temp;
            p = c; l = 2 * p; r = l + 1;
        }
        else break;
    }
    return 1;
}
 
int main(void) {
 
    int i, s, e, cnt;
    NODE d;
    scanf("%d %d %d", &M, &N, &Q);
    for (i = 1; i <= N; i++) { scanf("%d", &A[i]); } // 기존 자리잡은 학생의 컴위치
    for (i = 1; i <= Q; i++) { scanf("%d", &B[i]); } // 친구들의 순번
    //merge_sort(0, N - 1); //A배열을 sorting 해준다.
    for (i = 1; i <= N; i++) { // 앞에서부터 빈자리의 그릅을 힙트리에 push
        s = A[i - 1] + 1;
        e = A[i] - 1;
        cnt = e - s + 1;
        push(s, e, cnt);
    }
    // 맨 끝 마지막 그룹 push
    push(A[N] + 1, M, M - A[N]);
 
    for (i = N + 1; i <= B[Q]; i++) { // 기존 앉은 학생의 순번 다음부터 친구 마지막 순번까지만 탐색
        // pop한 그룹의 mid자리에 i번째 학생을 앉히고 왼쪽, 오른쪽 그룹을 다시 push
        pop(&d);
        int m = (d.s + d.e) / 2;
        A[i] = m;
        if (d.s < m) push(d.s, m - 1, m - 1 - d.s + 1); // 왼쪽 그룹 푸쉬
        if (m < d.e) push(m + 1, d.e, d.e - (m + 1) + 1); // 오른쪽 그룹 푸쉬
    }
 
    for (i = 1; i <= Q; i++) { printf("%d\n", A[B[i]]); } // Q명의 친구가 앉은 컴위치 인쇄
 
    return 0;
}