\(S\) をソートして靴下 index を振り直します。最適解において、ペアにするのは隣接する靴下のみとしてよいです。

靴下 \(i\) と \(i+1\) をペアにしたときの違和感を \(D_i\) とします。問題は「\(D_1,\dots,D_{N-1}\) から、隣接しない \(M\) 個の要素を選び、その和を最小化せよ」となります。（隣接する要素を選べないのは「\(i\) と \(i+1\) をペアにする」「\(i+1\) と \(i+2\) をペアにする」を同時に実現できないことに由来します）

この問題は ABC218H などで知られている通り、次のような貪欲法により解くことができます。

問題： \(A=(A_1,\dots,A_N)\) から、隣接しない \(K\) 個の要素を選び、その和を最小化せよ。

解法：

• スコアを \(0\) とする。
• 以下の操作を \(M\) 回繰り返す。
  • \(A\) の最小要素を \(A_i\) とする。スコアに \(A_i\) を加算する。\(A_i\) を \(A_{i-1}+A_{i+1}-A_i\) に置き換え、\(A_{i-1},A_{i+1}\) を \(A\) から削除し、順序を保って連結する。（範囲外の添字に対しては \(A_i=\infty\) と定める）
• 操作後のスコアが求める解である。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

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

  vector<ll> data({INF, INF});
  for(int i=0; i<n-1; i++){
    data.push_back(s[i+1]-s[i]);
  }
  data.push_back(INF);
  data.push_back(INF);
  
  n = data.size();
  vector<int> pre(n), nxt(n);
  iota(pre.begin(), pre.end(), -1);
  iota(nxt.begin(), nxt.end(), 1);
  
  priority_queue<pair<ll,int>> q;
  for(int i=0; i<n; i++){
    q.push({-data[i], i});
  }
  ll ans = 0;
  for(int x=0; x<m; x++){
    ll v;
    int i;
    while(true){
      v = q.top().first;
      i = q.top().second;
      q.pop();
      v = -v;
      if(data[i]==v) break;
    }
    ans += v;
    data[i] = data[pre[i]] + data[nxt[i]] - v;
    q.push({-data[i], i});
    // remove pre
    data[pre[i]] = INF;
    int k = pre[pre[i]];
    nxt[k] = i;
    pre[i] = k;
    // remove nxt
    data[nxt[i]] = INF;
    k = nxt[nxt[i]];
    nxt[i] = k;
    pre[k] = i;
  }

  cout << ans << endl;
}

実装例 (Python)

import heapq
N, M = map(int, input().split())
S = list(map(int, input().split()))
S.sort()

INF = 10**18
data = [INF]*2 + [S[i+1]-S[i] for i in range(N-1)] + [INF]*2
n = len(data)
pre = list(range(-1, n-1))
nxt = list(range(1, n+1))

q = [(v, i) for i, v in enumerate(data)]
heapq.heapify(q)
ans = 0
for _ in range(M):
  while True:
    v, i = heapq.heappop(q)
    if data[i] == v:
      break
  ans += v
  data[i] = data[pre[i]] + data[nxt[i]] - v
  heapq.heappush(q, (data[i], i))
  # remove pre
  data[pre[i]] = INF
  k = pre[pre[i]]
  nxt[k] = i
  pre[i] = k
  # remove nxt
  data[nxt[i]] = INF
  k = nxt[nxt[i]]
  nxt[i] = k
  pre[k] = i

print(ans)