题目描述

某公司基地搬迁后新规划了一条班车路线，沿途经过 N 个小区，需要从中选择 M 个小区作为上车点。小区的位置可以表示为一维坐标点 x1, x2, ..., xN。一个小区到上车点的距离是两点坐标差的绝对值。

目标是选取 M 个上车点，使得所有小区到最近上车点的距离总和最小，并返回这个最小值。

输入描述

• 第一行两个整数 N, M，分别表示小区数量和上车点数量（1 < M <= N <= 50）。
• 第二行 N 个不重复的整数 x1, x2, ..., xN，表示小区的位置（1 <= xi <= 1000000）。

输出描述

一个整数，表示所有小区到上车点的总距离的最小值。

样例输入

5 2
1 2 3 6 7

样例输出

3

题解思路

为了解决这个问题，我们可以使用 动态规划 方法，具体步骤如下：

动态规划设计

1. 定义状态：
   我们使用 dp[i][k] 表示从前 i 个小区中选 k 个上车点时的最小距离总和。
2. 状态转移方程：
   假设第 k 个上车点覆盖了从小区 j 到小区 i 的这段范围，其最小距离总和可以通过以下方式计算： dp[i][k] = min(所有可能的j) { dp[j-1][k-1] + cost[j][i] } 其中 cost[j][i] 表示从第 j 到第 i 小区的最小距离总和，这可以通过选择区间 [j, i] 的中位数来优化计算。 cost[j][i] 等于从 j 到 i 每个位置与该区间中位数之间的距离之和。
3. 边界条件：
   • dp[0][0] = 0：当没有小区也没有上车点时，距离自然为 0。
   • dp[i][0] = 无穷大：如果没有上车点，则无法满足条件，所以设置为无穷大。

代码实现

Python 代码

def min_total_distance(N, M, positions):
    # 预处理 cost[j][i]，表示第 j 到第 i 小区的最小距离总和
    cost = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(i, 0, -1):
            median = positions[(j + i - 1) // 2]  # 选择中位数
            cost[j][i] = sum(abs(positions[k - 1] - median) for k in range(j, i + 1))

    # 初始化 dp 数组
    dp = [[float('inf')] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    # 动态规划填表
    for i in range(1, N + 1):
        for k in range(1, M + 1):
            for j in range(1, i + 1):
                dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + cost[j][i])

    # 返回结果
    return dp[N][M]

# 测试样例
n, m = map(int, input().split())
positions = list(map(int, input().split()))
print(min_total_distance(n, m, positions))  # 输出: 3

C++ 代码

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int inf = 1e9;
int minTotalDistance(int N, int M, vector<int>& positions) {
    // 预处理 cost[j][i]
    vector<vector<int>> cost(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = i; j >= 1; --j) {
            int median = positions[(j + i - 1) / 2];  // 找中位数
            for (int k = j; k <= i; ++k) {
                cost[j][i] += abs(positions[k - 1] - median);
            }
        }
    }

    // 初始化 dp 数组
    vector<vector<int>> dp(N + 1, vector<int>(M + 1, inf));
    dp[0][0] = 0;

    // 动态规划
    for (int i = 1; i <= N; ++i) {
        for (int k = 1; k <= M; ++k) {
            for (int j = 1; j <= i; ++j) {
                dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + cost[j][i]);
            }
        }
    }

    // 返回结果
    return dp[N][M];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> positions(n);
    for (int i = 0; i < n; ++i) {
        cin >> positions[i];
    }
    cout << minTotalDistance(n, m, positions) << endl;  // 输出: 3
    return 0;
}

Java 代码

import java.util.*;

public class Main {
    static final int inf = 1000000000;
    public static int minTotalDistance(int N, int M, int[] positions) {
        int[][] cost = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = i; j >= 1; j--) {
                int median = positions[(j + i - 1) / 2]; 
                for (int k = j; k <= i; k++) {
                    cost[j][i] += Math.abs(positions[k - 1] - median);
                }
            }
        }

        int[][] dp = new int[N + 1][M + 1];
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], inf);
        }
        dp[0][0] = 0;

        for (int i = 1; i <= N; i++) {
            for (int k = 1; k <= M; k++) {
                for (int j = 1; j <= i; j++) {
                    dp[i][k] = Math.min(dp[i][k], dp[j - 1][k - 1] + cost[j][i]);
                }
            }
        }

        return dp[N][M];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] positions = new int[n];
        for (int i = 0; i < n; i++) {
            positions[i] = sc.nextInt();
        }
        System.out.println(minTotalDistance(n, m, positions));  // 输出: 3
    }
}

题目内容

某公司基地搬迁到新地点之后，新规划了一条班车路线，在这条路线上会经过 $N$ 个小区，计划在这些小区中挑选出 $M$ 个作为上车点，小区的位置可以用一维坐标上的点来表示，小区到上车点的距离为两个坐标点差值的绝对值。现在给定 $N$ 个小区的位置，即一维坐标上的整数点：$x1、x2、...、xN$ ，请计算选取 $M$ 上车点后，使得所有小区到最近上车点的距离总和尽可能小，并返回这个最小值。当该小区被作为上车点，该小区到上车点的距离为 $0$ 。

输入描述

第一行有两个整数，用空格隔开：$N$ $M$ ，$1<M<=N<= 50$

第二行有 $N$ 个没有重复的整数，用空格隔开，表示 $N$ 个小区的位置，$1<=xi<= 1000000$

输出描述

一个整数，表示所有小区到上车点的总和的最小值

样例1

输入

5 2
1 2 3 6 7

输出

3

说明

将上车点设置在 $2、6$ 这两个小区，可以使得所有小区到上车点的总距离最小为 $3$ 。

样例2

输入

10 5
1 2 3 6 7 11 22 44 50

输出

9

说明

将上车点设置在 $2、9、22、44、50$ 这 $5$ 个小区时，使得所有小区到上车点的总距离最小为 $9$ 。