問題一覧 > 通常問題

No.1734 Decreasing Elements

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : platinumplatinum / テスター : saksak
7 ProblemId : 6775 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-25 19:25:10

問題文

$N$ 項からなる非負整数列 $A = (A_1, A_2, \dots, A_N)$ があります。 すべての $i = 1, 2, \dots, N$ に対して $A_i = 0$ となるまで、高橋君は以下の操作を繰り返し行います。

操作:

  • $i = 1, 2, \dots, N$ のうち、$A_i > 0$ を満たす最小の $i$ を $j$ とする。このときの $A_j$ の値を $K$ とする。
  • $i = j, j+1, \dots, N$ それぞれに対して、$A_i \geq K$ であれば $A_i$ を $A_i-K$ に置き換える。そうでなければ何もしない。

この操作は有限回で終了することが証明できます。高橋君が操作を行う回数を求めてください。

入力

$N$
$A_1\ A_2 \dots A_N$

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

出力

答えを一行に出力してください。

サンプル

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

操作により数列 $A$ は以下のように変化します。
$(3, 1, 4)$ → $(0, 1, 1)$ → $(0, 0, 0)$
したがって求めるべき答えは $2$ です。

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

はじめから全ての要素が $0$ であれば一度も操作を行いません。

サンプル3
入力
17
1 0 54 21 87 79 79 82 12 28 41 2 53 26 22 80 19
出力
10

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