31068번 - 균형 잡힌 등급 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1153 | 141 | 114 | 16.474% |
문제
서울과학고의 자료구조 수업은 $N$명의 학생이 수강한다. 자료구조 수업은 중간고사와 기말고사가 존재하며, 각 시험의 점수는 $0$ 이상 $10^6$ 이하의 정수이다.
선생님은 학생들의 시험 점수를 바탕으로 학생들에게 '상', '중', '하' 중 하나의 등급을 부여하려고 한다. 이때 부여하는 등급은 다음 두 조건에 맞아야 한다.
- 각 등급은 적어도 한 명의 학생이 받아야 한다.
- 더 높은 등급을 받은 학생은 더 낮은 등급을 받은 학생보다 중간고사, 기말고사 점수가 모두 더 높아야 한다.
선생님은 불균형도를 최소화하도록 등급을 매기고자 한다. '상', '중', '하' 등급을 받은 사람의 수를 각각 $a$, $b$, $c$라고 하자. 이때 불균형도는 $\max(a,b,c) -\min(a,b,c)$로 정의된다.
가능한 불균형도의 최솟값을 구하여라.
입력
첫 줄에 학생의 수 $N$이 주어진다.
그 뒤 $N$개의 줄이 주어진다. 이들 중 $i$번째 줄에는 $i$번 학생의 중간고사와 기말고사 점수 $A_i$와 $B_i$가 띄어쓰기를 사이에 두고 주어진다.
출력
가능한 불균형도의 최솟값을 출력한다.
만약 선생님이 조건에 맞게 등급을 부여하는 것이 불가능하다면, -1을 출력한다.
제한
- $3\le N\le 2\times 10^5$
- $0\le A_i,B_i\le 10^6$ $(1\le i\le N)$
- 입력에 주어지는 모든 수는 정수이다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N \le 80$ |
| 2 | 20 | $N \le 600$ |
| 3 | 30 | $N \le 3\ 000$ |
| 4 | 40 | 추가 제한 조건이 없다. |
예제 입력 1
3 1 10 2 20 3 30
예제 출력 1
0
예제 입력 2
8 1 2 2 1 3 4 4 3 5 6 6 5 7 8 8 7
예제 출력 2
2
예제 입력 3
5 2 4 3 1 5 6 8 2 7 3
예제 출력 3
-1
노트
$\max(a,b,c)$와 $\min(a,b,c)$는 각각 $a$, $b$, $c$ 중 최댓값과 최솟값을 의미한다.
출처
School > 서울과학고등학교 > SciOI 2023 A-3번
- 문제를 만든 사람: 79brue
- 문제를 검수한 사람: mjhmjh1104, naeby, ncy09, utilforever, whqkrkt04
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호