問題一覧 > 通常問題

No.2036 Max Middle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : milkcoffeemilkcoffee / テスター : nok0nok0 rianoriano
26 ProblemId : 8254 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-10 13:23:26

問題文

長さ $N$ の整数列 $A$ が与えられます。 $A$ について、$A_i \neq A_{i+1} \ (1 \leq i \leq N-1)$ が成り立ちます。
あなたは整数列 $A$ に対して以下の操作を行うことができます。

  • $A_i< A_{i+1}$ かつ $A_{i+1}>A_{i+2}$ となる整数 $i \ (1 \leq i \leq N-2)$ を選ぶ。そして、 $A_{i+1}$ を $\mathrm{min}(A_{i},A_{i+2})-1$ で置き換える。
最大で何回操作を行うことができますか。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

  • $3 \leq N \leq 2 \times 10^5$
  • $-10^9 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
  • $A_i \neq A_{i+1} \ (1 \leq i \leq N-1)$
  • 入力は全て整数である。

    • 出力

    操作を行える回数の最大値を整数で出力してください。

    サンプル

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

    まず、 $i=1$ として操作を行うと、 $A=(2,1,3,-1)$ となります。
    次に、 $i=2$ として操作を行うと、 $A=(2,1,-2,-1)$ となります。
    これで $2$ 回操作を行うことができました。これより多い回数の操作を行うことはできません。

    サンプル2
    入力
    3
100 -100 100
    出力
    0

    $1$ 度も操作を行えない場合もあります。

    サンプル3
    入力
    3
-1000000000 0 -1000000000
    出力
    1

    操作後の値が $-10^9$ 未満になっても良いです。

    サンプル4
    入力
    7
-5 -21 0 10 9 30 29
    出力
    5

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