Official

C - 果物の箱詰め / Packing Apples in Boxes Editorial by kyopro_friends Editorial for printing

\(A\) を昇順にソートし、indexを振り直します。最適解において、どの箱も入れられているリンゴの番号は全て区間となります。

まず、空の箱があっても良いとしても答えは変化しません。なぜなら、空の箱があるとき、$K\leq N$ の仮定から、2個以上リンゴが入った箱があります。その箱から最も軽いリンゴを空の箱に移しても、ばらつき度の合計は大きくならないためです。

リンゴの番号が区間となっていない箱 $X$ があったとします。$X$ に入っているリンゴの番号の最大値と最小値の間にあり、$X$ に入っていないリンゴ $i$ があります。リンゴ $i$ が入っている箱を $Y$ とします。 リンゴ $i$ を $Y$ から $X$ に移すと、箱 $X$ のばらつき度は変化せず、箱 $Y$ のばらつき度は変化しないか小さくなります。よってこの操作で損をしません。この操作を繰り返すことにより、損をすることなく全ての箱のリンゴの番号を区間とすることができます。

よって問題は「数直線上の \(N\) 個の点を、\(K\) 個の区間で覆うとき、区間長の和を最小化せよ」となります。区間の端点として考える必要があるのは \(A\) に含まれる値のみであることから、この問題は「隣接要素の差の値 \(N-1\) 個から、捨てる要素 \(K-1\) 個を選んで、残りの和を最小化せよ」となります。

例：\(N=5,K=3,A=(2,4,7,10,15)\) のとき

これは隣接要素 \(N-1\) 個を全て求め、その上位 \(K-1\) 個を除いた和を取れば良く、 \(O(N\log N)\) で求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a.begin(), a.end());

  vector<int> d(n-1);
  for(int i=0; i<n-1; i++){
    d[i] = a[i+1] - a[i];
  }
  sort(d.begin(), d.end());

  int ans = 0;
  for(int i=0; i<n-k; i++){
    ans += d[i];
  }
  cout << ans << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
D = [A[i+1] - A[i] for i in range(N-1)]
D.sort()
print(sum(D[:N-K]))

posted:
last update: