| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 120 | 51 | 49 | 63.636% |
길이가 $N$인 순열 $a$가 있다. 피돌이와 피붕이가 다음과 같은 게임을 한다.
각 플레이어는 번갈아가며 턴을 가지고, 각 턴마다 다음 시행을 한다.
게임은 피돌이가 턴을 가진 상태로 시작한다.
$a$의 길이가 $1$이 됐을 때 $a_1$의 값이 게임의 점수가 된다. 피돌이는 점수를 최대화하고 싶고 피붕이는 점수를 최소화하고 싶다. 둘 모두 최적의 전략을 사용한다고 가정할 때 게임의 점수를 구해보자.
첫째 줄에 정수 $N$이 주어진다. $(1\leq N \leq 300 000)$
둘째 줄에 $N$개의 정수 $a_1, a_2, \cdots, a_N$가 공백으로 구분되어 주어진다. $N$개의 수는 $N$이하의 서로 다른 양의 정수임이 보장된다.
첫째 줄에 게임의 점수를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $a$는 오름차순이다. |
| 2 | 90 | 추가적인 제한은 없다. |
4 2 4 3 1
3
5 5 2 1 3 4
3
Contest > BOJ User Contest > 피갤컵 > 제3회 피갤컵 H번