問題一覧 > 通常問題

No.2029 Swap Min Max Min

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ 👑 ygussanyygussany
3 ProblemId : 8185 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-05 23:32:36

問題文

$(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もしくは右上の雲マークをクリックしてアカウントを作成してください。