問題一覧 > 通常問題

No.1391 ±1 Abs Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : chineristACchineristAC / テスター : eSeFeSeF
5 ProblemId : 5481 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-13 14:13:17

問題文

はじめに整数 $N,\ K$ と長さ $N$ の単調非減少整数列 $A=(A_1,\ A_2,\ \dots\ A_N)$ が与えられます。

長さ $N$ の整数列 $B=(B_1,\ B_2,\ \dots\ B_N)$ に対し、関数 $f_B(x)$ を以下のように定義します。

\begin{align} \displaystyle f_B(x) = \sum_{i=1}^{N}B_i \left|x-A_i \right| \end{align}

以下の条件を満たすすべての整数列 $B$ に対し $A_1 \leq x \leq A_N$ における $f_B(x)$ の最小値を考え、その中の最小値を求めてください。

条件
  • $i=1,\ 2,\ \dots\ N$ に対し $|B_i|=1$ が成り立つ
  • $i=1,\ 2,\ \dots\ N$ のうち、 $B_i=1$ が成り立つものはちょうど $K$ 個存在する

($21:30$ 単調増加整数列を単調非減少整数列に修正)

入力

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

  • $1\leq N \leq 2\times 10^5$
  • $0\leq K \leq N$
  • $-10^9 \leq A_i \leq 10^9\ (1\le i \le N)$
  • $A_i \leq A_{i+1}\ (1\le i \le N-1)$
  • 与えられる入力はすべて整数

出力

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

最後に改行してください。

サンプル

サンプル1
入力
4 2
-10 -9 2 6
出力
-27

たとえば $B=(1,\ 1,\ -1,\ -1)$ とすると $f_B(x)$ は $x=-10$ で最小値 $-27$ をとります。最小値がこれより小さくなるような $B$ は存在しないので $-27$ が答えになります。

サンプル2
入力
4 0
-7 -2 2 4
出力
-25

サンプル3
入力
15 8
-99 -99 -94 -90 -85 -52 -47 -30 -19 6 12 14 28 45 100
出力
-683

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