컴퓨터실

컴퓨터 실습실에는 총 M대의 컴퓨터가 일렬로 놓여있다. 이 컴퓨터는 왼쪽에 있는 것부터 순서대로 1~M의 번호가 매겨져 있다.
현재, 이 실습실에는 총 N명의 학생들이 이미 앉아있으며, 각각 들어온 순서에 따라 A1, A2, ..., AN번 컴퓨터 앞에 앉아있다. 곧 있으면 자습시간이 시작되기 때문에 총 M-N명의 학생이 더 와서 컴퓨터를 사용할 것이다.
각 학생들은 다른 학생이 자기 컴퓨터의 모니터를 보는 것을 싫어하므로 다음과 같은 방법으로 자리를 잡을 것이다.
1.    우선 학생이 없는 연속한 컴퓨터들의 그룹 중 가장 컴퓨터가 많은 그룹을 선택한다. 만약 이런 그룹이 여러 개라면 가장 왼쪽에 있는 그룹을 선택한다.
2.    그 다음, 선택한 그룹의 컴퓨터들 중 정 중앙에 있는 컴퓨터를 선택하여 자리를 잡는다. 만약 학생이 선택한 그룹의 컴퓨터가 짝수개인 경우 정 중앙 2개의 컴퓨터 중 왼쪽에 있는 컴퓨터에 자리를 잡는다.
정환이는 Q명의 친구들과 함께 팀 프로젝트를 해야 하기 때문에 Q명의 친구들이 어디에 앉을 지 알아야 한다. 다행히 정환이는 각 친구가 몇 번째로 실습실에 들어갔는지 알고 있다. 정환이를 도와 각 친구들의 위치를 구하시오.

입력

첫 번째 줄에는 컴퓨터의 수 M, 이미 자리를 잡은 학생의 수 N, 친구의 수 Q가 주어진다.
두 번째 줄에는 N개의 정수가 주어지는데, 이 값은 자리를 잡은 학생의 위치 Ai를 나타낸다. 이미 자리를 잡은 학생들은 앞서 말한 방법으로 자리를 잡지 않았을 수도 있음에 유의하여라.
세 번째 줄에는 Q개의 정수가 주어지는데, 이 값은 각 친구가 실습실에 들어간 순서 Bi를 의미한다. ( 이미 자리를 잡은 학생들 N명 중 정환이의 친구가 있을 수도 있다. )
1 ≤ A1 < A2 < . . . < AN ≤ M, 1 ≤ B1 < B2 < . . . < BQ ≤ M.
1 ≤ Q ≤ 105, N ≤ M, 1 ≤ N ≤ 105, 1 ≤ M ≤ 3*105

출력

출력은 총 Q개의 줄로 이루어진다. i번째 줄에는 i번째 친구가 자리잡은 컴퓨터의 번호를 출력한다. 

입력 예시

7 1 4
4
2 3 4 5

출력 예시

2
6
1
3
#include <stdio.h>
struct data
{
 int gap, start;
}heap[300010];
int a[300010], 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)
{
 heap[++last].gap = g;
 heap[last].start = s;

 for (int i = last; i > 1 && comp(i, i / 2)>0; i /= 2) {
  swap(i, i / 2);
 }
}
struct data pop(void)
{
 swap(1, last);
 last--;
 for (int i = 1, j = 2; j <= last; i = j, j *= 2) {
  if (j + 1 <= last && comp(j + 1, j)>0) j++;
  if (comp(i, j)<0)    swap(i, j);
  else break;
 }
 return heap[last + 1];
}

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 (int i = N + 1; i <= b[Q]; i++) {
  d = pop();
  e = d.start + d.gap - 1;
  n = (d.start + e) / 2;
  a[i] = n;
  if (n > d.start)push(n - d.start, d.start);
  if (e > n)push(e - n, n + 1);
 }

 for (int i = 1; i <= Q; i++) {
  printf("%d\n", a[b[i]]);
 }
 return 0;
}

댓글

댓글 쓰기

이 블로그의 인기 게시물

어민

한 작은 나라에서는 대부분의 시민들이 어부이며, 그 나라의 모든 마을은 직선 해변을 따라 건설된 직선 도로에 위치해 있다. 마을의 어부들은 엄청난 양의 물고기를 잡았으나 예전처럼 물고기를 좋아하지 않아서 이웃 나라의 가난하고 배고픈 아이들을 입양하기로 결정했다. 하나의 긴 직선 도로가 해변을 따라 모든 마을을 연결한다. 따라서 각 도시(첫 번째와 마지막 도시는 제외)는 두 이웃 마을에 직접 연결된다. 1년에 한 명의 어린이가 1톤의 물고기를 먹는다. 어떤 마을에서 잡힌 물고기의 양은 그 마을에서 먹거나 다른 마을로 옮길 수 있다. 도로를 이용해서 옮겨야 하는데 이용에 따른 세금이 부과된다. 1km당 1톤의 물고기를 세금으로 내야 한다. 각 마을마다 동등한 수의 가난한 아이들이 입양되기를 원한다. 각 마을에 수용될 수 있는 아이들의 최대 수를 결정하는 프로그램을 작성하시오. 모든 물고기가 잡히고 저렴하게 운반된 물고기를 먹을 수 있다는 조건이다. 입력 첫 번째 줄에는 마을 수 N(1≤N≤100,000, 정수)이 입력된다 두 번째 줄부터 N줄에 걸쳐 마을 정보가 입력된다. 마을 정보는 두 개의 정수A, B이며 공백으로 구분되어 입력된다. A는 도시의 위치이며 B는 잡힌 물고기 양이다. (1≤A≤1,000,000,000, 단위는 km) (0≤B≤1,000,000,000, 단위는 톤) 마을 정보는 도로 위치에 따라 오름차순으로 정렬되어 입력된다. 출력 각 마을에 동일한 수로 입양될 수 있는 최대 아이들 수를 출력하라 입력 예시 3 1 0 2 21 4 0 출력 예시 6 도움말 2 번 마을에서 6톤+1톤(세금) = 7톤을 1번 마을로 보내고, 4번 마을에 6톤+2톤(세금) = 8톤을 보낼 수 있다. 남은 6톤을 2번 마을 아이들을 먹일 수 있으므로 최대 수는 6명이다. 입력 예2 3 5 70 15 100 1200 20   출력 예2 20 ...
자세한 내용 보기

최소비용 포장

사탕 공장에서는 요구에 따라 다양한 개수의 사탕을 담고 있는 포장을 하고 있다. 어느 날 갑자기 대형 이벤트가 생겨서 공장에 있는 모든 사탕들을 풀어서 하나로 포장 해야 한다.   A, B, C 3 개의 사탕 포장이 있을 때 이 포장들을 한번에 하나로 합칠 수는 없고, 한번에 2개씩만 합칠 수 있다. 예를 들면 A와 B를 먼저 합친 후 C를 다시 합치거나 A와 C를 먼저 합치고 B를 합치기, 혹은 B와 C를 먼저 합치고 A를 합칠 수 있다.   사탕 포장을 풀었다가 다시 합치는 순서는 매우 중요한데, 그 이유는 그 순서에 따라 전체 비용이 달라지기 때문이다.   사탕 포장 A와 B에 각각 a개와 b개의 사탕이 들어있다고 할 때 이 둘을 합치는 비용은 a + b라고 한다. 그러므로 A와 B를 먼저 합치고 C를 합치는 경우 그 전체 비용은 a + b + a + b + c이며, B와 C를 먼저 합치고 A를 합치는 비용은 b + c + b + c + a 이므로 그 둘은 서로 같지 않을 수 있다.   예를 들어, 각각 2, 2, 5개가 포장되어 있다면 A(2)와 B(2)를 합치는 비용은 4. 합쳐진 것(4)과 C(5)를 합치는 비용은 9로 총 13이 최소비용이다.   현재 공장에 포장되어 있는 포장 개수 N과 각각 포장에 들어있는 사탕의 개수 ni가 주어질 때, 이들을 하나로 합치는데 들어가는 비용의 최소(C)를 구하라. 입력 첫 번째 줄에는 포장 개수 N(1<=N<=5000)이 주어진다. 두 번째 줄에는 포장에 들어있는 사탕의 개수 ni(1<=ni<=100)가 주어진다. 출력 최소 비용을 출력한다. 입력 예시 3 2 2 5 출력 예시 13 #include <stdio.h> #define MAX 5003 int N; int ni[MAX]; int tree[MAX]...
자세한 내용 보기

구슬집어넣기

철수의 동생이 다니는 학교에서는 ‘구슬 집어넣기 게임’ 선풍적인 인기를 끌고 있다. 철수 동생은 반 친구들과 이 게임의 성적을 놓고 경쟁을 하고 있다.    어느 날, 철수의 동생이 시무룩한 얼굴을 하고 집에 들어왔다. 친구들보다 좋은 성적을 내지 못했다고 우울했던 것이다. 그래서 철수는 동생을 위해 게임에서 최고 성적을 내는 방법을 알려주는 프로그램을 만들기로 했다.   게임은 다음 룰에 의해 진행된다.   1. 게임판에는 빨간구슬, 파란구슬, 벽, 그리고 목표구멍이 있다. 2.  플레이어는 총 10회 게임판을 기울일 수 있다. (방향 : 상하좌우) 3.  플레이어가 게임판을 기울이게 되면 해당 방향으로 빨간구슬과 파란구슬이 한 칸 이동한다. 4.  이동방향에 벽이 있는 구슬은 움직일 수 없다. 5.  이동 시 빨간 구슬과 파란 구슬이 같은 위치로 움직여 부딪히는 경우 구슬이 깨지므로, 게임 실패다. 6.  파란구슬이 목표구멍으로 들어가는 것은 게임 실패다. 7.  기울임 횟수가 10회를 넘어서면 게임 실패다. 8.  빨간 구슬이 목표구멍으로 들어가는 것이 이 게임의 목표이다. 9.  적은 횟수를 기울여 해결할수록 많은 높은 점수를 얻을 수 있다.   기본적으로 게임판의 가장자리는 구슬이 게임판 밖으로 빠져나가지 못하도록 벽으로 둘러쌓여 있다.   철수는 우선 이 게임에서 문제를 해결할 수 있는 가장 적은 횟수를 알고 싶다. 이를 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다. 이후부터 T개의 테스트 케이스 셋트가 주어진다. 셋트의 첫 번째 줄에는 게임판의 행(R)과 열(C)이 순서대로 주어진다. (3<=R,C<=15) 셋트의 두 번째 줄부터 게임판의 행만큼 게임판의 상황이 주어진다. (...
자세한 내용 보기