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

2019年7月24日2020年9月8日

問題

方針

\( 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 \) 個の和を取ったものが答えになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  if (k == n) {
    cout << "0\n";
    return 0;
  }
  vector<ll> e(n - 1);
  for (int i = 0; i < n - 1; i++) {
    e[i] = a[i + 1] - a[i];
  }
  sort(e.begin(), e.end());
  ll cost = 0;
  for (int i = 0; i < n - k; i++) {
    cost += e[i];
  }
  cout << cost << "\n";
  return 0;
}