Минимальная сумма растояний между точками

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, k,mns=100000000000,in=0;
    cin >> n >> k;
    vector<long long> h(n+1);
    for (int i = 1; i <=n; ++i)
        cin >> h[i];
    long long sum=0,sum2=0;
    for(int i=1; i<=n; i++)
    {
        sum=-1;
        sum2=-1;
        if(i-k>=1)
        {
            sum++;
            for(int j=i-k;j<=i;j++)
                sum+=(abs(h[i]-h[j]));
        }
        else if(i+k<=n)
        {
            sum2++;
            for(int j=i;j<=n;j++)
            sum2+=(abs(h[i]-h[j]));
        }
       // cout<<sum<<" "<<sum2<<" "<<i<<endl;
        if(sum<mns and sum>-1)
        {
            mns=sum;
            in=i;
        }
        if(sum2<mns and sum2>-1)
        {
            mns=sum2;
            in=i;
        }
    }
    cout<<h[in]<<" "<<mns;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
 
int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> coordinates(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> coordinates[i];
    }
    //сортировка координат точек
    std::sort(coordinates.begin(), coordinates.end());
    long long minSum = std::numeric_limits<long long>::max();
    int chosenPoint;
    //перебор возможных начальных точек
    for (int i = 0; i <= n - k; ++i) {
        long long currentSum = 0;
        //расчёт суммы расстояний до ближайших k точек
        for (int j = i; j < i + k; ++j) {
            //проверка, чтобы избежать выхода за границы вектора
            if (j < n - 1) {
                currentSum += std::abs(coordinates[j] - coordinates[j + 1]);
            }
        }
        //обновление минимальной суммы и выбранной точки, если текущая сумма меньше
        if (currentSum < minSum) {
            minSum = currentSum;
            chosenPoint = coordinates[i + k / 2];
        }
    }
    std::cout << chosenPoint << " " << minSum << std::endl;
    return 0;
}

#include <cassert>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
 
struct State
{
  using XS = std::vector<int>;
  XS &xs;
  unsigned i; // текущая точка
  unsigned il, ir; // [il, ir] - k-окрестность
  unsigned sum; // текущая сумма расстояний
 
  State(XS &xs, unsigned k) : xs(xs), i(0), il(0), ir(k)
  {
    std::sort(xs.begin(), xs.end());
    sum = sum_k();
  }
 
  unsigned sum_k() const 
  { // Эта функция используется только один раз - при инициализации
    // Все остальные вызовы делаются изнутри `assert`
    // По техническим причинам допускается, что i находится за пределами [il, ir]
    assert(i < xs.size());
    assert(il < ir && ir < xs.size());
 
    unsigned sum = 0;
    for (unsigned j = il; j <= ir; ++j)
      sum += std::abs(xs[j] - xs[i]);
 
    return sum;
  }
 
  void shift_lr()
  { // По техническим причинам допускается, что i находится за пределами [il, ir]
    assert(i < xs.size());
    assert(il < ir && ir < xs.size());
 
    ++il, ++ir;
    sum += std::abs(xs[ir] - xs[i]);
    sum -= std::abs(xs[il - 1] - xs[i]);
 
    assert(sum == sum_k());
  }
 
  bool shift_i()
  {
    assert(il < ir && ir < xs.size());
    assert(il <= i && i <= ir);
 
    if (++i == xs.size())
      return false;
 
    // Здесь i мог выйти за [il, ir]
    // Все равно исправяляем сумму для нового i
 
    assert(xs[i - 1] <= xs[i]);
    unsigned delta = xs[i] - xs[i - 1];
    assert(il < i && i - 1 <= ir);
    unsigned nl = i - il, nr_old = ir - (i - 1);
    sum += delta * nl;
    assert(sum >= delta * nr_old);
    sum -= delta * nr_old;
 
    assert(sum == sum_k());
 
    // ... а затем исправляем ситуацию с [il, ir]
 
    assert(il < i && i <= ir + 1);
    if (i > ir)
      shift_lr();
 
    assert(il < i && i <= ir);
    return true;
  }
 
  void minimize()
  { // Сдвигаем [il, ir] пока это уменьшает сумму
    assert(il <= i && i <= ir);
    for (; il < i && ir + 1 < xs.size(); shift_lr())
    { // il - кандидат на выход, ir + 1 - кандидат на вход в окрестность
      assert(xs[il] <= xs[i] && xs[i] <= xs[ir + 1]);
      unsigned delta_l = xs[i] - xs[il], delta_r = xs[ir + 1] - xs[i];
      if (delta_r >= delta_l)
        break;
    }
  }
};
 
int main() 
{
  unsigned n = 0, k = 0;
  std::cin >> n >> k;
 
  State::XS xs(n);
  for (int &x : xs)
    std::cin >> x;
 
  State s(xs, k);
  unsigned min_sum = s.sum, min_i = s.i;
 
  while (s.shift_i())
  {
    s.minimize();
 
    if (s.sum < min_sum)
    {
      min_sum = s.sum;
      min_i = s.i;
    }
  }
 
  std::cout << xs[min_i] << " " << min_sum << std::endl;
}

int coord (int n, int k, int *x, unsigned long long &dist)
{
  // 1 ≤ k < n ≤ 10^5
  // −10^9 ≤ xi ≤ 10^9
 
  int i, j, tmp, point_x, count;
  unsigned long long sum;
 
  // заполнение массива (через ГПСЧ) - для тестов и прочего
  // int num = 1e9;
  // for (i = 0; i < n; i++)
  //   x[i] = rand() % (2 * num + 1) - num;
 
  // сортировка (простая)
  for (i = 0; i < n - 1; i++)
    for (j = i + 1; j < n; j++)
      if (x[j] < x[i])
      {
        tmp = x[j];
        x[j] = x[i];
        x[i] = tmp;
      }
 
  // считаем сумму расстояний для точки x[0]
  sum = 0;
  point_x = x[0];
  for (i = 1; i <= k; i++)
    sum += x[i];
  sum -= k * x[0];
  dist = sum;
  if (dist == 0)
    return point_x;
 
  // проход по точкам и окрестностям
  // наверно можно оптимизировать подсчет расстояний не только
  // при проверке (всех) точек окрестности для текущей точки x[i],
  // но и когда еще меняется точка x[i], но тут я пас
  for (i = 0; i < n; i++)
  {
    sum = 0;
    count = 0;
 
    for (j = i - k; j <= i + k; j++)
      if (j != i && j >= 0 && j < n)
      {
        count++;
 
        sum += abs(x[i] - x[j]);
 
        if (count > k)
        {
          count--;
          tmp = (j == i + k) ? j - k : j - k - 1;
          sum -= abs(x[i] - x[tmp]);
        }
 
        if (count == k  && sum < dist)
        {
          dist = sum;
          point_x = x[i];
 
          if (dist == 0)
            return point_x;
        }
      }
  }
 
  return point_x;
}

  const n = 10;
  int k = 2, x[n] = {4, 4, 19, 2, 14, 9, 11, 9, 3, 20};
  unsigned long long dist;
 
  // выводим значение координаты (x[i]):
  // coord(n, k, x, dist)
 
  // выводим сумму расстояний:
  // dist

#include <cassert>
#include <vector>
#include <algorithm>
#include <iostream>
 
int main() 
{
  unsigned n = 0, k = 0;
  std::cin >> n >> k;
 
  std::vector<int> xs(n);
  for (int &x : xs)
    std::cin >> x;
 
  std::sort(xs.begin(), xs.end());
 
  std::vector<unsigned long long> sums(n);
  for (unsigned i = 1; i < n; ++i)
    sums[i] = sums[i - 1] + (unsigned long long) (xs[i] - xs[i - 1]) * i;
 
  auto sum_left = [&](unsigned il, unsigned i)
  {
    assert(il <= i && i < xs.size());
    assert(xs[il] <= xs[i] && sums[il] <= sums[i]);
    unsigned long long raw_sum = sums[i] - sums[il];
    unsigned long long excess_sum = (unsigned long long) (xs[i] - xs[il]) * il;
    assert(excess_sum <= raw_sum);
    return raw_sum - excess_sum;
  };
 
  auto sum_right = [&](unsigned i, unsigned ir)
  {
    assert(i <= ir && ir < xs.size());
    assert(xs[i] <= xs[ir]);
    unsigned long long full_sum = (unsigned long long) (xs[ir] - xs[i]) * (ir - i + 1);
    unsigned long long complementary_sum = sum_left(i, ir);
    assert(complementary_sum <= full_sum);
    return full_sum - complementary_sum;
  };
 
  auto sum_k = [&, k](unsigned il, unsigned i)
    { return sum_left(il, i) + sum_right(i, il + k); };
 
  unsigned i = 0, il = 0;
  unsigned long long sum = sum_k(il, i);
  // Сумма для точек в диапазоне [il, il+k] относительно i
 
  unsigned min_i = i;
  unsigned long long min_sum = sum;
 
  for (++i; i < n; ++i)
  {
    // Проверим, что i не вышло за [il, il+k]
    if (il + k < i)
      ++il;
 
    assert(il <= i && il + k >= i);
 
    sum = sum_k(il, i);
    // Сумма для текущего [il, il+k]
 
    // Сдвигаем дипазон [il, il+k] вправо, пока это уменьшает сумму
    for (; il < i && il + 1 + k < xs.size(); ++il)
    {
      unsigned long long next_sum = sum_k(il + 1, i);
      if (next_sum >= sum)
        break;
 
      sum = next_sum;
    }
 
    if (sum < min_sum)
    {
      min_sum = sum;
      min_i = i;
    }
  }
 
  std::cout << xs[min_i] << " " << min_sum << std::endl;
}