Покрытие

#include <cmath>
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::string;
using std::vector;

int inv = 0;
int len;
int knum;
vector<int> ar;

vector<int> MergeSort(vector<int> ar) {
  int len = ar.size();
  if (len == 1) {
    return ar;
  }
  vector<int> lt;
  vector<int> rt;
  for (int id = 0; id < len / 2; ++id) {
    lt.push_back(ar[id]);
  }
  for (int id = len / 2; id < len; ++id) {
    rt.push_back(ar[id]);
  }
  lt = MergeSort(lt);
  rt = MergeSort(rt);
  int ln = lt.size();
  int rn = rt.size();
  int lid = 0;
  int rid = 0;
  vector<int> res;
  while (lid < ln || rid < rn) {
    if (lid < ln && rid < rn) {
      if (lt[lid] <= rt[rid]) {
        res.push_back(lt[lid]);
        lid++;
      } else {
        res.push_back(rt[rid]);
        rid++;
        inv += ln - lid;
      }
    } else if (lid < ln) {
      res.push_back(lt[lid]);
      lid++;

    } else if (rid < rn) {
      res.push_back(rt[rid]);
      rid++;
    }
  }
  return res;
}

bool Check(int md) {
  int left = 0;
  int cnt = knum;
  for (int id = 1; id < len; ++id) {
    if (ar[id] - ar[left] <= md) {
      continue;
    }
    cnt--;
    left = id;
  }
  return cnt >= 0;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  cin >> len >> knum;
  ar.resize(len);
  for (int& el : ar) {
    cin >> el;
  }
  ar = MergeSort(ar);
  int lt = 1;
  int rt = ar[len - 1] - ar[0];
  int md;
  while (rt - lt > 1) {
    md = (lt + rt) / 2;
    bool ok = Check(md);
    if (ok) {
      rt = md;
    } else {
      lt = md;
    }
  }
  cout << rt;
}