2020牛客寒假算法基础集训营2 H题施魔法

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
int dp[N], pre, a[N], n, k;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  sort(a + 1, a + 1 + n);
  pre = -a[1];
  for (int i = 1; i < k; ++i) dp[i] = 2e9;
  for (int i = k; i <= n; ++i) {
    dp[i] = pre + a[i];
    pre = min(pre, dp[i - k + 1] - a[i - k + 2]);
  }
  cout << dp[n];
  return 0;
}