On one line there are n houses. Give you an array of integer means the the position of each house. Now you need to pick k position to build k post office, so that the sum distance of each house to the nearest post office is the smallest. Return the least possible sum of all distances between each village and its nearest post office.

Have you met this question in a real interview?

Yes

Example

Given array a =[1,2,3,4,5], k = 2.
return3.

Challenge

Could you solve this problem inO(n^2)time ?

line w[i][j] need to spilit into two range i - m m - j to calculate

class Solution {

public:

/**

 * @param A an integer array

 * @param k an integer

 * @return an integer

 */

int postOffice(vector<int>& A, int k) {

    // Write your code here

    if (A.empty() || k >= A.size()) {

        return 0;

    }

    int n = A.size();

    sort(A.begin(), A.end());

    vector<vector<int>> f(k + 1, vector<int>(n + 1));

    vector<vector<int>> w(n + 1, vector<int>(n + 1, 0));

    vector<int> prefixSum(n + 1, 0);

    for (int i = 1; i <= n; ++i) {

        prefixSum[i] = prefixSum[i - 1] + A[i - 1];

    }



    for (int i = 1; i <= n; ++i) {

        for (int j = i + 1; j <= n; ++j) {

            int m = (j - i) / 2 + i;

            w[i][j] = (m - i + 1) * A[m - 1] - (prefixSum[m] - prefixSum[i - 1]) + prefixSum[j] - prefixSum[m - 1] - (j - m + 1) * A[m - 1];

        }

    }



    for (int i = 1; i <= n; ++i) {
        f[1][i] = w[1][i];
    }



    for (int i = 2; i <= k; ++i) {

        for (int j = i + 1; j <= n; ++j) {

            f[i][j] = INT_MAX;

            for (int l = 0; l < j; ++l) {

                if (f[i][j] > f[i - 1][l] + w[l + 1][j]) {

                    f[i][j] = f[i - 1][l] + w[l + 1][j];

                }

            }

        }

    }



    return f[k][n];

}
};