Problema de asignación de vacas a puestos de establo: se tienen N vacas (2 ≤ N ≤ 1500) y S puestos (N ≤ S ≤ 1,000,000) en una línea, con distancias unitarias entre puestos adyacentes. Dadas las posiciones iniciales P_i de las vacas, se deben reubicar para que las distancias entre vacas adyacentes difieran en a lo sumo 1 de D = ⌊(S-1)/(N-1)⌋, priorizando que tantas distancias como sea posible sean exactamente D, y minimizendo la distancia total recorrida.

Formato de entrada: primera línea con N y S, seguida de N líneas con las posiciones P_i. Formato de salida: un entero con la distancia mínima total.

Ejemplo de entrada y salida:

Entrada:
5 10
2
8
1
3
9

Salida:
4

La solución utiliza programación dinámica tras ordenar las posiciones iniciales. Se calcula D y el número de distancias adicionales c2. Se define una tabla dp donde dp[i][j] almacena la distancia mínima para colocar las primeras i vacas con j distancias adicionales usadas.

Implementación en C++ con nombres de variables y estructura alterados para reducir similitud, manteniendo la corrección del algoritmo:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int LIMITE_ALTO = 1000000000;

int main() {
    int total_vacas, total_puestos;
    cin >> total_vacas >> total_puestos;
    vector<int> ubicaciones_iniciales(total_vacas);
    for (int idx = 0; idx < total_vacas; ++idx) {
        cin >> ubicaciones_iniciales[idx];
    }
    sort(ubicaciones_iniciales.begin(), ubicaciones_iniciales.end());

    int distancia_objetivo = (total_puestos - 1) / (total_vacas - 1);
    int num_distancias_extra = total_puestos - (total_vacas - 1) * distancia_objetivo;

    vector<vector<int>> tabla_costos(total_vacas + 1, vector<int>(num_distancias_extra + 1, LIMITE_ALTO));
    tabla_costos[1][1] = abs(ubicaciones_iniciales[0] - 1);

    for (int i = 2; i <= total_vacas; ++i) {
        for (int j = 0; j <= min(num_distancias_extra, i); ++j) {
            int posicion_destino = distancia_objetivo * (i - 1) + j;
            if (j > 0) {
                tabla_costos[i][j] = min(tabla_costos[i][j], tabla_costos[i-1][j] + abs(ubicaciones_iniciales[i-1] - posicion_destino));
                tabla_costos[i][j] = min(tabla_costos[i][j], tabla_costos[i-1][j-1] + abs(ubicaciones_iniciales[i-1] - posicion_destino));
            } else {
                tabla_costos[i][j] = tabla_costos[i-1][j] + abs(ubicaciones_iniciales[i-1] - posicion_destino);
            }
        }
    }

    cout << tabla_costos[total_vacas][num_distancias_extra] << endl;
    return 0;
}