두 배 2s 1024MB

問題

길이 N인 양의 정수열 A_1,\dots,A_N이 주어진다. 이 수열을 오름차순으로 만들려 한다.

수열 A_1,\dots,A_N이 오름차순이라는 것은, 각 i (1\le i \le N-1)에 대해 A_i \le A_{i+1}이라는 것이다.

수열 A를 오름차순으로 만들기 위해, 수열 A에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

연산을 최소 횟수로 적용해서 A를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.

[제약 조건]

주어지는 모든 수는 정수이다.

1 \le N \le 250,000

1 \le A_i \le 1,000,000 (1\le i \le N)

첫 번째 줄에 N이 주어진다.

두 번째 줄에 A_1, \dots, A_N이 주어진다.

첫 번째 줄에 답을 출력한다.

番号	点数	条件
#1	12点	각 i(1\le i \le N)에 대해, A_i = 1 또는 A_i = 2
#2	10点	각 i(1\le i \le N)에 대해, A_i = 2^{k_i}를 만족하는 0 이상의 정수 k_i가 존재
#3	11点	N \le 10
#4	19点	각 i (1 \le i \le N)에 대해, A_i=2 또는 A_i=3
#5	20点	각 i (1 \le i \le N-1) 에 대해, A_i \ge A_{i+1}
#6	28点	추가 제약 조건 없음

5keyboard_return
3space_bar 1space_bar 4space_bar 1space_bar 5

A_2, A_4에 각각 두 번씩 연산을 적용하면 된다. 연산을 적용한 이후에 수열 A는 [3,4,4,4,5]가 된다.

5keyboard_return
3space_bar 1space_bar 5space_bar 1space_bar 5

A_2에 두 번, A_4에 세 번, A_5에 한 번 연산을 적용하면 된다. 연산을 적용한 이후에 수열 A는 [3,4,5,8,10]가 된다.

5keyboard_return
1space_bar 2space_bar 3space_bar 4space_bar 5

タグ

KOI 1차 2024 초2/중1

ログインしないとコードを書けません。