問題一覧 > 通常問題

No.2304 Distinct Elements

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : ShirotsumeShirotsume / テスター : hamamuhamamu ygussanyygussany
2 ProblemId : 9478 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-03 01:28:50

問題文

長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます．あなたは，この数列に対し以下の操作を好きな回数行うことができます．

  • $1 \leq i \leq N$ を満たす整数 $i$ を選ぶ．$A_i$ を $A_i + 1$ か $A_i - 1$ のうち好きな方に置き替える．

あなたの目標は，$1 \leq i \lt j \leq N$ を満たす任意の整数対 $(i, j)$ について， $A_i \neq A_j$ である状態にすることです．そのために必要な操作の最小回数を求めてください．

制約

  • 入力は全て整数
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$

入力

入力は標準入力から以下の形式で与えられる．

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

必要な操作の最小回数を出力せよ．

サンプル

サンプル1
入力
3
2 2 2
出力
2

例えば， $(2, 2, 2) \rightarrow (1, 2, 2) \rightarrow (1, 2, 3)$ とすることで， $2$ 回の操作で目標が達成できます．

サンプル2
入力
4
1 2 2 3
出力
2

例えば， $(1, 2, 2, 3) \rightarrow (1, 1, 2, 3) \rightarrow (0, 1, 2, 3)$ とすることで， $2$ 回の操作で目標が達成できます．

操作によって $A$ の要素が $0$ や負になっても構いません．

サンプル3
入力
4
1 1 1 1
出力
4
サンプル4
入力
9
9 9 8 2 4 4 3 5 3
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。