[Codeforces] Educational Round 69 (Div. 2) C. Array Splitting

問題

方針

\( a \) が昇順に整列されていることが重要です。

偏差に着目する

\( e_i = a_{i + 1} – a_{i} \) とすると、\( l < r \) として、

\[a_r – a_l = \sum_{k = l}^{r-1} e_k\]

となります。これは、部分配列 \( a_l, a_{l+1}, \cdots , a_r \) における分割コストを表しています。このコストを最小化するような分割の仕方を考えます。

貪欲法

\( k = n \) のとき、\( n \) 個の部分配列に分割されるので、コストは \( 0 \) です。\( k = 1 \) のとき、分割コストは \( a_n – a_1 \) となります。\( 2 \leq k \leq n – 1 \) のときを考えると、\( c = a_n – a_1\) として、\( c \) から任意に \(  k \) 個 の \( e_i \) をなくすことができます。よって、コストの最小値は、\( e \) を昇順に並び替え、小さい順に \( n – k \) 個の和を取ったものが答えになります。

コード