No.2029 Swap Min Max Min
タグ : / 解いたユーザー数 71
作問者 :
Shirotsume
/ テスター :
👑 
ygussany
とりゐ
問題文
$(1, 2, \dots, N)$ を並べ替えた長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。
あなたは初めに、 $A$ の 隣接する $2$ 要素を入れ替える操作を好きな回数（$0$ 回でもよい）行います。
その後、各 $i$ $(1 \leq i \leq N - 1)$ について $B_i = \min(A_i, A_{i + 1})$ で定める長さ $N - 1$ の数列 $B$ を作ります。
以下に示す $2$ つの値 $X, Y$ を求めてください。
- $B$ の最大値として考えられる最小の値 $X$
- 上記の $X$ を達成するために必要な操作の最小回数 $Y$
制約
- 入力は全て整数
- $2 \leq N \leq 2 \times 10^5$
- $A$ は $(1, 2, \dots, N)$ を並べ替えた数列
入力
入力は標準入力から以下の形式で与えられる。
$N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
$X, Y$ を以下の形式で出力せよ。最後に改行すること。
$X$ $Y$
サンプル
サンプル1
入力
3 2 3 1
出力
1 1
最初、数列 $A = (2, 3, 1)$ です。初めに、操作を $1$ 回行って $(2, 3, 1) \rightarrow (2, 1, 3)$ とします。
この $A$ に対して、 $B = (\min(2, 1), \min(1, 3)) = (1, 1)$ となるので、$B$ の最大値は $1$ となります。
どのように操作をしても、 $B$ の最大値は $1$ 未満にはならないので、 $X = 1$ です。また、操作回数の最小値は $1$ 回なので $Y = 1$ となります。
サンプル2
入力
5 1 2 3 4 5
出力
2 3
まず、$3$ 回の操作を行って、 $(1, 2, 3, 4, 5) \rightarrow (1, 3, 2, 4, 5) \rightarrow (3, 1, 2, 4, 5) \rightarrow (3, 1, 4, 2, 5)$ とします。
この $A$ に対し、 $B = (1, 1, 2, 2)$ となるので、 $B$ の最大値は $2$ となります。
どのように操作をしても、 $B$ の最大値は $2$ 未満にはならないので、 $X = 2$ です。また、操作回数の最小値は $3$ 回なので $Y = 3$ となります。
サンプル3
入力
14 14 12 8 3 9 10 1 6 4 11 5 2 7 13
出力
7 9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。