| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 272 | 49 | 48 | 21.333% |
길이 $N$의 순열 $P$가 있다. 당신은 한 연산에서 다음과 같은 연산을 최대 10ドル,000円$회 할 수 있다.
예를 들어 $[2,1,4,3,5]$에서 $l=2, r=4$인 연산을 사용한다면, $[2,\underline{3},\underline{4},\underline{1},5]$가 된다.
연산을 최대 10ドル,000円$번만 하여 순열 $P$를 오름차순으로 정렬하는 방법을 구해보자. 가능한 방법이 여러 가지라면, 사용한 연산의 비용의 합이 최소인 방법을 구해보자.
첫째 줄에 $N$이 주어진다. $(1 \leq N \leq 5,000円)$
둘째 줄에 $P_1, P_2, \cdots, P_N$가 공백으로 구분되어 주어진다.
첫째 줄에 연산의 횟수 $Q$를 출력한다. $(0 \leq Q \leq 10,000円)$
다음 $Q$개의 줄에 $i$번째 연산 $l_i$와 $r_i$를 공백으로 구분하여 출력한다. $(1 \leq l_i \leq r_i \leq N)$
순열 $P$를 최소한의 비용으로 정렬할 수 있는 방법이 여러 가지라면, 아무 방법이나 출력한다.
5 5 2 3 4 1
3 1 5 2 4 3 3
각 연산 이후 $P$는 다음과 같이 변화한다.
$[5, 2, 3, 4, 1] \rightarrow [\underline{1}, \underline{4}, \underline{3}, \underline{2}, \underline{5}] \rightarrow [1, \underline{2}, \underline{3}, \underline{4}, 5] \rightarrow [1, 2, \underline{3}, 4, 5]$
연산의 횟수를 최소화 할 필요는 없음에 유의하라.
6 1 3 2 5 4 6
3 2 5 2 4 3 5
$[1, 3, 2, 5, 4, 6] \rightarrow [1, \underline{4}, \underline{5}, \underline{2}, \underline{3}, 6] \rightarrow [1, \underline{2}, \underline{5}, \underline{4}, 3, 6]\rightarrow [1, 2, \underline{3}, \underline{4}, \underline{5}, 6]$
6 6 5 4 3 2 1
1 1 6
길이 $N$의 순열은 1ドル$부터 $N$까지의 수가 정확히 한 번 등장하는 수열을 말한다.
예를 들어, $[3,5,1,2,4]$와 $[1,3,2]$는 순열이지만, $[2,3,2]$또는 $[0]$은 순열이 아니다.
두 정수 $a$와 $b$에 대해 $a \operatorname{mod} b$는 $a$를 $b$로 나눈 나머지를 의미한다.
연산을 10ドル,000円$번 이하로 하여 주어진 순열을 항상 정렬할 수 있음을 보일 수 있다.
University > 한양대학교 > 2025 한양대학교 ALOHA 벚꽃컵 > Div. 1 C번