캠핑장 자리 배정
실버 III의견: 0
인기 캠핑장에 \(K\)개의 자리가 있다. \(N\)개의 예약 그룹이 도착 시각 순서대로 자리를 배정받는다. 자리를 배정하는 규칙은 다음과 같다.
- 현재 가장 일찍 빈 자리를 배정한다.
- 빈 시각이 같은 자리가 여럿이면 자리 번호가 작은 쪽을 배정한다.
- 그룹이 도착할 때 배정된 자리가 아직 사용 중이라면, 그 자리가 빌 때까지 기다린 뒤 사용을 시작한다.
각 그룹의 도착 시각 \(a_i\)와 이용 시간 \(d_i\)가 주어질 때, 기다림이 발생한 그룹의 수와 각 그룹에 배정된 자리 번호를 구하여라.
- \(1 \le K \le 1\,000\)
- \(1 \le N \le 100\,000\)
- \(0 \le a_i \le 10^9\), 입력은 \(a_i\) 오름차순
- \(1 \le d_i \le 10^9\)
첫째 줄에 자리의 수 \(K\)와 그룹 수 \(N\)이 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 도착 시각 \(a_i\)와 이용 시간 \(d_i\)가 공백으로 구분되어 주어진다. 그룹은 도착 시각 오름차순으로 주어진다.
첫째 줄에 기다림이 발생한 그룹의 수를 출력한다.
다음 \(N\)개의 줄에 각 그룹에 배정된 자리 번호를 순서대로 출력한다.
2 4
1 3
2 5
4 2
7 1
0
1
2
1
1
캠핑장이 \(2\)개이고, 그룹 \(4\)개가 차례로 도착한다. 그룹 \(1, 2\)는 각각 자리 \(1, 2\)를 즉시 배정받는다. 그룹 \(3\)은 도착 시각 \(4\)에 자리 \(1\)이 비어 배정받는다. 그룹 \(4\)는 도착 시각 \(7\)에 자리 \(1\)이 \(6\)에 비어 즉시 배정된다. 대기하는 그룹은 \(0\)개다.
1 3
0 5
3 2
6 1
2
1
1
1
캠핑장이 \(1\)개뿐이다. 그룹 \(1\)은 즉시 배정. 그룹 \(2\)는 도착 \(3\)에 자리가 아직 안 비어(\(5\)에 빔) 대기. 그룹 \(3\)도 도착 \(6\)에 자리가 아직 안 비어(\(7\)에 빔) 대기. 총 \(2\)개 그룹이 기다린다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
캠핑장 자리 배정
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
캠핑장 자리 배정