No.1391 ±1 Abs Sum

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 :

chineristAC / テスター :

eSeF

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{array}{r} f_{B} (x) = \sum_{i = 1}^{N} B_{i} | x - A_{i} | \end{array}

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

条件

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

 $N K$ 
 $A_{1} A_{2} \dots A_{N}$

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

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

4 2
-10 -9 2 6

-27

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

4 0
-7 -2 2 4

-25

15 8
-99 -99 -94 -90 -85 -52 -47 -30 -19 6 12 14 28 45 100

-683

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