Untitled

#include <vector>
#include <algorithm>
#include <iostream>
#include <climits>

using namespace std;

int getMinTotalDistance(vector<int> dist_centers) {
    int n = dist_centers.size();
    
    // Sort the distribution centers
    sort(dist_centers.begin(), dist_centers.end());

    // Calculate prefix sums of positions
    vector<int> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + dist_centers[i];
    }

    // Helper function to calculate the cost of placing one warehouse for a given range
    auto get_cost = [&](int start, int end) {
        int mid = (start + end) / 2;
        int median = dist_centers[mid];
        int cost = 0;
        for (int i = start; i <= end; ++i) {
            cost += abs(dist_centers[i] - median);
        }
        return cost;
    };

    // dp[i][k]: minimum cost for placing k warehouses up to the i-th distribution center
    vector<vector<int>> dp(n + 1, vector<int>(3, INT_MAX));
    dp[0][0] = 0;

    // Fill the dp table
    for (int k = 1; k <= 2; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i][k] = min(dp[i][k], dp[j][k - 1] + get_cost(j, i - 1));
            }
        }
    }

    // Return the result: minimum cost for placing 2 warehouses for all n centers
    return dp[n][2];
}

// Example usage
int main() {
    vector<int> dist_centers = {1, 2, 3};
    cout << getMinTotalDistance(dist_centers) << endl;  // Output: 1
    
    dist_centers = {1, 6};
    cout << getMinTotalDistance(dist_centers) << endl;  // Output: 0