P5612. K-Median 聚类

场次：2026年10月10日 · 来源：CodeFun2000 P5612

题目描述

K-Median 按划分做聚类：样本之间用曼哈顿距离（L1），簇中心取该簇在每一维上的中位数，因此离群点不容易把中心拉偏。

给定 n 个样本，每个样本有 d 个浮点特征。请按下列固定流程把样本分成 k 个簇，并输出簇编号、最终中心和 inertia。

初始化：取下标 0 到 k-1 的样本作为 k 个簇的初始中心。

分配：把每个样本分到曼哈顿距离最近的中心。到多个中心的距离相同时，分到编号最小的簇。

更新：若某个簇在本轮分配后没有样本，则该簇中心保持不变；否则，用簇内样本在每一维上的中位数替换该簇中心。

重复分配与更新，直到中心变化量小于 tol，或迭代次数达到 max_iter。tol 固定为 $10^{-4}$ ，max_iter 固定为 100。中心变化量是所有簇、所有维度上，新旧中心坐标绝对差的总和。

曼哈顿距离为

$dist(x,y)=\sum_i |x_i-y_i|$

一维中位数：将数值升序排列后，个数为奇数时取正中间的一项，个数为偶数时取正中间两项的算术平均（可以是浮点数）。例如 $[1,3,5,9]$ 的中位数是 $(3+5)/2=4$ 。

输入格式

第一行三个整数 n、d、k，依次为样本数、特征维数、簇数。

接下来 n 行，每行 d 个浮点数，表示一个样本的特征。

$1 \le n \le 5000$

$1 \le d \le 20$

$1 \le k \le \min(100, n)$

每个特征值都属于 $[-10^4, 10^4]$ 。

输出格式

第一行输出 n 个整数，为最后一轮分配得到的簇编号（从 0 到 k-1），相邻整数之间用一个空格分隔。

接下来 k 行，按簇编号从 0 到 k-1 输出本轮更新后的中心。每行 d 个浮点数，保留小数点后 6 位，相邻数之间用一个空格分隔。空簇输出被保留下来的中心。

最后一行输出 inertia，即每个样本到其所属簇中心的曼哈顿距离之和，保留小数点后 6 位。

示例

示例 1

输入：

输出：

0 0
000000 5.000000
000000

说明：

$k=1$ 时，初始中心就是样本 0，即 $(2,8)$ 。三个样本都分进簇 0。

第 1 维排序为 $2,4,6$ ，中位数是 4；第 2 维排序为 $1,5,8$ ，中位数是 5。新中心为 $(4,5)$ 。

再分配一次，中心不再变化，迭代停止。

inertia 为各样本到 $(4,5)$ 的曼哈顿距离之和：

$|2-4|+|8-5|=5$ ， $|6-4|+|1-5|=6$ ， $|4-4|+|5-5|=0$ ，合计 11。

示例 2

输入：

输出：

0 1 1
500000 1.500000
500000 6.500000
000000

说明：

初始中心：簇 0 为 $(1,1)$ ，簇 1 为 $(4,2)$ 。

第 1 轮分配：

样本 0 $(1,1)$ ：到簇 0 为 0，到簇 1 为 4，分到簇 0
样本 1 $(4,2)$ ：到簇 0 为 4，到簇 1 为 0，分到簇 1
样本 2 $(5,5)$ ：到簇 0 为 8，到簇 1 为 4，分到簇 1
样本 3 $(8,8)$ ：到簇 0 为 14，到簇 1 为 10，分到簇 1

簇 0 只有一个样本，中心仍是 $(1,1)$ 。簇 1 的第 1 维为 $4,5,8$ ，中位数 5；第 2 维为 $2,5,8$ ，中位数 5。变化量为 $|5-4|+|5-2|=4$ 。

第 2 轮，中心为 $(1,1)$ 与 $(5,5)$ ：

样本 0：距离 0 与 8，分到簇 0
样本 1：距离 $|4-1|+|2-1|=4$ 与 $|4-5|+|2-5|=4$ ，相等，取编号更小的簇 0
样本 2：距离 8 与 0，分到簇 1
样本 3：距离 14 与 6，分到簇 1

簇 0 含 $(1,1)$ 、 $(4,2)$ ，中位数为 $((1+4)/2,(1+2)/2)=(2.5,1.5)$ 。簇 1 含 $(5,5)$ 、 $(8,8)$ ，中位数为 $(6.5,6.5)$ 。变化量为 $|2.5-1|+|1.5-1|+|6.5-5|+|6.5-5|=5$ 。

第 3 轮，中心为 $(2.5,1.5)$ 与 $(6.5,6.5)$ ：

样本 0：距离 2 与 11，分到簇 0
样本 1：距离 2 与 7，分到簇 0
样本 2：距离 6 与 3，分到簇 1
样本 3：距离 12 与 3，分到簇 1

划分和中心都不再变化，迭代停止。簇编号为 0 0 1 1。

inertia：

$|1-2.5|+|1-1.5|=2$ ， $|4-2.5|+|2-1.5|=2$ ， $|5-6.5|+|5-6.5|=3$ ， $|8-6.5|+|8-6.5|=3$ ，合计 10。

解题思路

第一步：理解问题本质

K-Median 和常见的 K-Means 只差在“中心怎么算”：

	中心	对应的距离	目标函数
K-Means	簇内均值	欧氏距离（L2）	平方误差和
K-Median	簇内逐维中位数	曼哈顿距离（L1）	绝对误差和

为什么 L1 距离下的最优点是中位数？把某一维单独拎出来看，这一维对总距离的贡献是 $\sum_i |x_i - c|$ 。当 $c$ 落在排序后的中间位置时，左右两边的样本个数相同，无论往左还是往右移动一点，减少的距离和增加的距离正好抵消，所以中位数（偶数个时中间两项之间任意一点，题目取算术平均）就是让这个和最小的位置。

举个直观的例子：某一维的取值是 $0, 0, 0, 0, 100$ 。中位数是 $0$ ，均值是 $20$ 。均值被那个 $100$ 拉走了，而中位数留在大多数样本身边——这就是题面说的“离群点不容易把中心拉偏”。

本题把整个流程都固定了：初始化用哪几个样本、距离怎么算、平局怎么判、空簇怎么办、什么时候停，全部写死在题面里。所以这题不是让我们设计聚类算法，而是一字不差地按规范模拟。真正的难点全在细节：平局、空簇、停止条件、输出顺序。

第二步：暴力解法：每轮全量重算

最直接的做法就是照着题面的四句话写四段循环：

centers = [s[:] for s in samples[:k]]      # 初始化：前 k 个样本的副本
labels = [0] * n
for _ in range(100):
    # 分配：每个样本找最近的中心
    for i in range(n):
        best, best_dist = 0, l1_distance(samples[i], centers[0], d)
        for j in range(1, k):
            dist = l1_distance(samples[i], centers[j], d)
            if dist < best_dist:           # 严格小于才换，天然处理平局
                best, best_dist = j, dist
        labels[i] = best

    # 更新：非空簇逐维取中位数，空簇保留原中心
    new_centers = []
    for j in range(k):
        group = [samples[i] for i in range(n) if labels[i] == j]
        if group:
            new_centers.append([median_of([row[t] for row in group]) for t in range(d)])
        else:
            new_centers.append(centers[j])

    # 停止：所有簇、所有维度上的中心变化量
    delta = sum(abs(new_centers[j][t] - centers[j][t])
                for j in range(k) for t in range(d))
    centers = new_centers
    if delta < 1e-4:
        break

这个写法完全正确，时间复杂度是每轮 $O(nkd)$ ，但常数偏大： $n$ 最大 $5000$ 、 $k$ 最大 $100$ 、 $d$ 最大 $20$ ，一轮就是 $10^7$ 次绝对值运算，而迭代次数最坏会接近 $100$ 。

第三步：优化解法：逐维累加 + 提前剪枝

分配与更新这两步有三处可以省：

1. 距离逐维累加，超过当前最优就放弃。

曼哈顿距离是 $d$ 个非负数相加：

dist(x,c)=\sum_{t=0}^{d-1}|x_t-c_t|

它是单调递增的：前几维的部分和一旦已经不小于当前最优距离，后面几维只会让它更大，不可能反超。绝大多数中心在前几维就会被排除掉，实际只算了两三个维度：

dist = 0.0
for t in range(d):
    dist += abs(x[t] - c[t])
    if dist >= best_dist:      # 部分和已不小于最优，剩下的维度只会更大
        break
else:                          # 完整算完且始终小于最优，才更新答案
    best_dist, best = dist, j

注意这里用的是 >=：距离相等时我们希望保留先枚举到的、编号更小的簇，所以相等就直接放弃后面的候选。

2. 平局处理不需要额外代码。

因为 $j$ 是从 $0$ 到 $k-1$ 递增枚举的，只要“严格更小才替换”，最终留下的就是距离最小的那些簇里编号最小的那个。这比先算出所有距离、再用 min(..., key=(距离, 编号)) 排一次更省事，也更不容易写错。

3. 更新这一步只需要按列排序。

簇内样本在每一维上是独立的，中位数只需要把该维的取值排序后取中间。把所有维度一起排序没有意义，还会让比较次数变多。

需要说明的是：剪枝只压低常数，最坏复杂度仍然是每轮 $O(nkd)$ ——因为数据真的很难区分时，每个中心都要算完 $d$ 维。

第四步：完整实现细节

1. 轮次的顺序：先分配，再更新

题面要求输出“最后一轮分配得到的簇编号”和“本轮更新后的中心”。也就是说每一轮的动作顺序固定为：

用当前中心分配 -> 用新分配更新中心 -> 计算变化量 -> 判断是否停止

输出时，簇编号来自这一轮的分配结果，中心来自这一轮的更新结果，两者是同一个轮次的产物，不能错位。

可以用示例 1 验证这一点：最后一轮更新后的中心是 $(4,5)$ ，inertia 用它算出 $5+6+0=11$ ；如果误用更新前的初始中心 $(2,8)$ ，会得到 $0+11+5=16$ 。

2. 中位数的两种情况

奇数个：正中间那一个；
偶数个：中间两项的算术平均，结果可能是 $.5$ 。

所以取中位数的函数统一返回 float，避免整数除法把 $.5$ 截掉。

3. 空簇：中心原样保留

某一轮分配后如果某个簇一个样本都没有，它没有中位数可算，题面要求保留原中心。这个保留的中心在下一轮仍然参与距离比较，也可能重新吸引到样本。

4. 中心变化量

\Delta=\sum_{j=0}^{k-1}\sum_{t=0}^{d-1}\left|new_{j,t}-old_{j,t}\right|

是所有簇、所有维度的绝对差之和。它和“最大位移”“欧氏距离”都不是一回事。空簇的新旧中心相同，贡献为 $0$ 。

5. inertia 用最终结果算

\text{inertia}=\sum_{i=0}^{n-1}dist\left(x_i,\ center_{label_i}\right)

必须在迭代结束后，用最终中心和最终分配算一次，而不是每轮累加。

6. 输出格式

中心与 inertia 都保留 $6$ 位小数。浮点运算可能出现 -0.0，格式化前把绝对值极小的数归零，避免输出 -0.000000。

完整代码实现

import sys

TOL = 1e-4       # 中心变化量的收敛阈值
MAX_ITER = 100   # 迭代次数上限


def median_of(values):
    """一维中位数：奇数个取正中间一项，偶数个取中间两项的算术平均。"""
    ordered = sorted(values)
    m = len(ordered)
    mid = m // 2
    if m % 2 == 1:
        return float(ordered[mid])
    # 偶数个：中间两项求和后除以 2，结果是 .0 或 .5，double 可以精确表示
    return (ordered[mid - 1] + ordered[mid]) / 2.0


def l1_distance(x, y, dims):
    """曼哈顿距离：逐维取绝对差再求和。"""
    total = 0.0
    for t in range(dims):
        total += abs(x[t] - y[t])
    return total


def kmedian(samples, k, dims):
    """按题面流程迭代，返回 (最后一轮的分配, 本轮更新后的中心)。"""
    n = len(samples)

    # 初始化中心：直接取前 k 个样本的副本，后面会整体替换，不能和样本共用列表
    centers = [samples[i][:] for i in range(k)]
    labels = [0] * n

    for _ in range(MAX_ITER):
        # ---------- 分配 ----------
        for idx in range(n):
            x = samples[idx]
            best = 0
            best_dist = l1_distance(x, centers[0], dims)

            for j in range(1, k):
                c = centers[j]
                dist = 0.0
                for t in range(dims):
                    dist += abs(x[t] - c[t])
                    # 距离只会越加越大，一旦不严格小于当前最优，
                    # 就不可能再成为更近的簇，直接放弃这个候选
                    if dist >= best_dist:
                        break
                else:
                    # 只有严格更小才替换：距离相等时保留编号更小的簇，
                    # 因为 j 是从小到大枚举的，先到者即为编号最小者
                    best_dist = dist
                    best = j

            labels[idx] = best

        # ---------- 更新 ----------
        # 按簇收集样本，空簇在这里表现为空列表
        members = [[] for _ in range(k)]
        for idx in range(n):
            members[labels[idx]].append(samples[idx])

        new_centers = []
        for j in range(k):
            group = members[j]
            if not group:
                # 空簇没有样本可算中位数，题目要求保留原中心
                new_centers.append(centers[j])
                continue
            # 每一维单独取中位数，所以按列取值后排序
            new_centers.append(
                [median_of([row[t] for row in group]) for t in range(dims)]
            )

        # 中心变化量：所有簇、所有维度上新旧坐标绝对差的总和
        delta = 0.0
        for j in range(k):
            old, new = centers[j], new_centers[j]
            for t in range(dims):
                delta += abs(new[t] - old[t])

        centers = new_centers
        if delta < TOL:
            break

    return labels, centers


def format_float(value):
    """保留 6 位小数，并把 -0.000000 归一成 0.000000。"""
    if abs(value) < 5e-7:
        value = 0.0
    return f"{value:.6f}"


def solve():
    """读取输入、完成聚类并按要求输出。"""
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return

    n = int(tokens[0])
    d = int(tokens[1])
    k = int(tokens[2])
    if n <= 0 or d <= 0 or k <= 0:
        return

    # 样本按行切分：每 d 个数是一个样本
    values = list(map(float, tokens[3:3 + n * d]))
    samples = [values[i * d:(i + 1) * d] for i in range(n)]

    labels, centers = kmedian(samples, k, d)

    # 第一行：最后一轮分配的簇编号
    print(" ".join(str(x) for x in labels))

    # 接下来 k 行：本轮更新后的中心
    for center in centers:
        print(" ".join(format_float(v) for v in center))

    # 最后一行：inertia = 每个样本到自己所属簇中心的曼哈顿距离之和
    inertia = 0.0
    for idx in range(n):
        inertia += l1_distance(samples[idx], centers[labels[idx]], d)
    print(format_float(inertia))


if __name__ == "__main__":
    solve()

NumPy 版本

以下版本使用 NumPy。只有在评测环境允许第三方库时才能提交；CodeFun2000 的普通 Python 环境不一定安装 NumPy。

import sys

import numpy as np

TOL = 1e-4       # 中心变化量的收敛阈值
MAX_ITER = 100   # 迭代次数上限


def kmedian(samples, k):
    """按题面流程迭代，返回 (最后一轮的分配, 本轮更新后的中心)。

    samples 是 (n, d) 的 float64 矩阵；整轮的距离、中位数、变化量都用
    数组一次算完，不再对每个样本、每个中心写循环。
    """
    n = samples.shape[0]

    # 初始化中心：直接取前 k 个样本的行，copy 保证后面整体替换时不影响样本表
    centers = samples[:k].copy()
    labels = np.zeros(n, dtype=np.int64)
    dists = np.empty((k, n), dtype=np.float64)

    for _ in range(MAX_ITER):
        # ---------- 分配 ----------
        # 第 j 行是全部样本到第 j 个中心的曼哈顿距离：(n, d) 逐元素相减取绝对值，
        # 再按列顺序累加。用 cumsum 取最后一列而不是 sum(axis=1)，是为了让累加
        # 顺序与逐项求和一致，避免 float64 的末位差异影响 6 位小数的输出
        for j in range(k):
            dists[j] = np.cumsum(np.abs(samples - centers[j]), axis=1)[:, -1]

        # argmin 返回第一个最小值的下标，天然满足「距离相同时取编号更小的簇」
        labels = dists.argmin(axis=0)

        # ---------- 更新 ----------
        # 空簇没有样本可算中位数，题面要求保留原中心
        new_centers = centers.copy()
        for j in range(k):
            group = samples[labels == j]
            if group.shape[0] > 0:
                # 逐列取中位数：np.median 奇数个取中间项，偶数个取中间两项平均
                new_centers[j] = np.median(group, axis=0)

        # 中心变化量：所有簇、所有维度上新旧坐标绝对差的总和
        # ravel 按行优先展平，cumsum 逐项累加，顺序与逐簇逐维求和一致
        delta = np.cumsum(np.abs(new_centers - centers).ravel())[-1]

        centers = new_centers
        if delta < TOL:
            break

    return labels, centers


def format_float(value):
    """保留 6 位小数，并把 -0.000000 归一成 0.000000。"""
    if abs(value) < 5e-7:
        value = 0.0
    return f"{value:.6f}"


def solve():
    """读取输入、完成聚类并按要求输出。"""
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return

    n = int(tokens[0])
    d = int(tokens[1])
    k = int(tokens[2])
    if n <= 0 or d <= 0 or k <= 0:
        return

    # 样本按行切分：一次读成 (n, d) 的二维数组
    samples = np.array(tokens[3:3 + n * d], dtype=np.float64).reshape(n, d)

    labels, centers = kmedian(samples, k)

    # 第一行：最后一轮分配的簇编号
    print(" ".join(str(int(x)) for x in labels))

    # 接下来 k 行：本轮更新后的中心
    for center in centers:
        print(" ".join(format_float(v) for v in center))

    # 最后一行：inertia = 每个样本到自己所属簇中心的曼哈顿距离之和
    # 先逐维累加得到每个样本的距离，再一次逐样本累加：两段都用 cumsum，
    # 保持与「样本内逐维相加、样本间再累加」完全相同的求和顺序
    row_dists = np.cumsum(np.abs(samples - centers[labels]), axis=1)[:, -1]
    inertia = np.cumsum(row_dists)[-1]
    print(format_float(inertia))


if __name__ == "__main__":
    solve()

这一版的三个关键点：

距离矩阵：samples - centers[j] 用广播得到 $n\times d$ 的差，取绝对值后沿维度方向逐项累加，就得到每个样本到第 $j$ 个中心的曼哈顿距离； $k$ 行拼成 $k\times n$ 的 dists，再 argmin(axis=0) 一次得到全部样本的分配。argmin 返回第一个最小值，正好对应题面的「距离相同时取编号更小的簇」，不需要额外写比较；
中位数：np.median(group, axis=0) 逐列取中位数，奇数个取中间项、偶数个取中间两项平均，与题面的一维中位数定义一致；空簇那一行不覆盖，等于保留原中心；
求和不换顺序：delta、inertia 都用 np.cumsum 而不是 np.sum。np.sum 的成对求和更快也更精确，但累加顺序与纯 Python 版不同，在 $10^8$ 量级上会差出最后几位，而这里要打印 6 位小数。inertia 是「先算每个样本的距离、再逐样本累加」两段求和，所以先用 cumsum(axis=1)[:, -1] 得到每个样本的距离，再对这条长度为 $n$ 的数组做一次 cumsum。

示例推演

样例 1：k=1，中心被中位数拉到 (4,5)

初始中心是样本 0，即 $(2,8)$ 。

第 1 轮分配：只有一个簇，三个样本都归簇 0，得到 0 0 0。

第 1 轮更新：

第 1 维取值 $2,6,4$ ，排序后 $2,4,6$ ，奇数个取正中间，中位数 $4$ ；
第 2 维取值 $8,1,5$ ，排序后 $1,5,8$ ，中位数 $5$ 。

新中心为 $(4,5)$ ，变化量 $|4-2|+|5-8|=2+3=5$ ，远大于 $10^{-4}$ ，继续。

第 2 轮分配：中心还是唯一一个，仍然是 0 0 0。

第 2 轮更新：三个样本没变，中位数还是 $(4,5)$ ，变化量 $0<10^{-4}$ ，停止。

输出 inertia（用最终中心 $(4,5)$ ）：

|2-4|+|8-5|=5,\quad |6-4|+|1-5|=6,\quad |4-4|+|5-5|=0

合计 $11$ 。

样例 2：k=2，中途出现距离平局

初始中心：簇 0 为样本 0 $(1,1)$ ，簇 1 为样本 1 $(4,2)$ 。

第 1 轮分配

样本	坐标	到簇 0	到簇 1	分到
0	$(1,1)$	0	4	簇 0
1	$(4,2)$	4	0	簇 1
2	$(5,5)$	8	4	簇 1
3	$(8,8)$	14	10	簇 1

分配结果 0 1 1 1。

第 1 轮更新

簇 0 只有 $(1,1)$ ，中位数就是 $(1,1)$ ；
簇 1 的第 1 维是 $4,5,8$ ，中位数 $5$ ；第 2 维是 $2,5,8$ ，中位数 $5$ ，所以中心变成 $(5,5)$ 。

变化量 $|1-1|+|1-1|+|5-4|+|5-2|=0+0+1+3=4$ ，继续。

第 2 轮分配（中心 $(1,1)$ 与 $(5,5)$ ）

样本	到簇 0	到簇 1	分到
0 $(1,1)$	0	8	簇 0
1 $(4,2)$	4	4	簇 0（平局，取编号更小）
2 $(5,5)$	8	0	簇 1
3 $(8,8)$	14	6	簇 1

分配结果 0 0 1 1。

第 2 轮更新

簇 0 含 $(1,1)$ 、 $(4,2)$ ，第 1 维 $1,4$ 的中位数是 $2.5$ ，第 2 维 $1,2$ 的中位数是 $1.5$ ；
簇 1 含 $(5,5)$ 、 $(8,8)$ ，中位数是 $(6.5,6.5)$ 。

变化量 $|2.5-1|+|1.5-1|+|6.5-5|+|6.5-5|=1.5+0.5+1.5+1.5=5$ ，继续。

第 3 轮分配（中心 $(2.5,1.5)$ 与 $(6.5,6.5)$ ）

样本	到簇 0	到簇 1	分到
0 $(1,1)$	2	11	簇 0
1 $(4,2)$	2	7	簇 0
2 $(5,5)$	6	3	簇 1
3 $(8,8)$	12	3	簇 1

分配结果仍是 0 0 1 1。

第 3 轮更新：两簇的成员和上一轮完全一样，中位数还是 $(2.5,1.5)$ 与 $(6.5,6.5)$ ，变化量 $0<10^{-4}$ ，停止。

输出 inertia：

|1-2.5|+|1-1.5|=2,\quad |4-2.5|+|2-1.5|=2

|5-6.5|+|5-6.5|=3,\quad |8-6.5|+|8-6.5|=3

合计 $2+2+3+3=10$ 。

复杂度分析

步骤	时间复杂度	空间复杂度	说明
分配	$O(n\cdot k\cdot d)$ 每轮	$O(n)$	逐维累加，超过当前最优立即剪枝
更新	$O(n\cdot d\log n)$ 每轮	$O(n\cdot d)$	按簇把每一维取值排序取中位数
变化量	$O(k\cdot d)$ 每轮	$O(k\cdot d)$	新旧坐标绝对差求和
总计	$O(iter\cdot(nkd+n\,d\log n))$	$O(n\cdot d+k\cdot d)$	$iter\le100$ ，即至多 100 轮

$n\le5000$ 、 $k\le100$ 、 $d\le20$ 、 $iter\le100$ ，最坏情况下需要上亿次基本运算。剪枝让实际计算量通常远小于上界，因为绝大多数中心在前几维就会被排除。如果数据更难区分，还可以用三角不等式做更强的下界剪枝（见“扩展思考”）。

易错点总结

1. 平局必须取编号最小的簇

j 从小到大枚举、只用“严格小于”替换当前最优，就自动满足这条规则。一旦写成 <=，平局时会换成编号更大的簇，后续的分配和中位数都会跟着变。

2. 偶数个样本的中位数是中间两项的平均值

四个样本 $1,3,5,9$ 的中位数是 $(3+5)/2=4$ ，不是 $3$ 也不是 $5$ 。平均值可能是 $.5$ ，所以中位数函数要返回浮点数。

3. 空簇的中心保持不变

空簇没有样本可算中位数，但它原来的中心还要继续参与下一轮的距离比较。比如三个样本完全相同、 $k=2$ 时，所有样本都会并入编号更小的簇 0，簇 1 一直是空簇，它的中心始终是初始值。

4. 变化量是所有坐标差的总和

不是最大位移，也不是平方和。示例 2 第 2 轮的变化量是 $1.5+0.5+1.5+1.5=5$ ，只算簇 0 的位移会得到 $2$ 。

5. 输出的是“先分配、后更新”的同一轮

簇编号来自这一轮的分配，中心来自这一轮的更新。不要用本轮分配去配上一轮的中心，也不要拿最后一轮中心重新分配一次再输出——题面只要求“最后一轮分配”和“本轮更新后的中心”。

6. inertia 要用最终中心和最终分配

迭代过程中不要累加 distance，因为中心和分配每轮都在变。结束后按 $dist(x_i, center_{label_i})$ 算一次才对。

7. 停止条件用严格小于，同时保留迭代上限

$delta<10^{-4}$ 才停；同时外层循环必须是 range(100)，防止一直不收敛时死循环。中心坐标要么是样本值，要么是中间两项的平均值，通常几轮内就会稳定。

8. 输出浮点格式

保留 $6$ 位小数，并注意不要把 -0.0 打印成 -0.000000。中位数恰好为 $0$ 且符号为负时最容易出现这种情况。

扩展思考

K-Median 与 K-Means 的关系：两者都是“分配 → 更新”的交替优化，区别只在更新规则。L1 + 中位数对离群点更稳健；L2 + 均值可以用质心公式直接算，但会被极端值拉偏。
inertia 单调不增：每轮分配只会让样本离中心更近或不变，更新又让簇内距离和取到该簇在 L1 下的最小值，所以 inertia 单调下降并最终稳定。这也解释了为什么算法一定会停。
对初始化敏感：本题固定用前 $k$ 个样本作初始中心，结果完全可复现。如果换成随机初始化，可能会掉进不同的局部最优，需要多跑几次取 inertia 最小的那次。
更强的剪枝：对任意两个中心 $a,b$ 和样本 $x$ ，三角不等式给出 $dist(x,b)\ge dist(a,b)-dist(x,a)$ 。用上一轮已经算出的距离做下界，可以把候选中心从 $k$ 个压到个位数，K-Means 里的 Elkan 算法用的就是这类下界。
高维的麻烦： $d$ 越大，L1 距离的区分度越低，剪枝越难生效，这也是维度灾难的一个侧面。

P5612. K-Median 聚类

题目描述

输入格式

输出格式

示例

示例 1

示例 2

解题思路

第一步：理解问题本质

第二步：暴力解法：每轮全量重算

第三步：优化解法：逐维累加 + 提前剪枝

第四步：完整实现细节

1. 轮次的顺序：先分配，再更新

2. 中位数的两种情况

3. 空簇：中心原样保留

4. 中心变化量

5. inertia 用最终结果算

6. 输出格式

完整代码实现

NumPy 版本

示例推演

样例 1：k=1，中心被中位数拉到 (4,5)

样例 2：k=2，中途出现距离平局

复杂度分析

易错点总结

1. 平局必须取编号最小的簇

2. 偶数个样本的中位数是中间两项的平均值

3. 空簇的中心保持不变

4. 变化量是所有坐标差的总和

5. 输出的是“先分配、后更新”的同一轮

6. inertia 要用最终中心和最终分配

7. 停止条件用严格小于，同时保留迭代上限

8. 输出浮点格式

扩展思考

相关题目

自测

题目描述​

输入格式​

输出格式​

示例​

示例 1​

示例 2​

解题思路​

第一步：理解问题本质​

第二步：暴力解法：每轮全量重算​

第三步：优化解法：逐维累加 + 提前剪枝​

第四步：完整实现细节​

1. 轮次的顺序：先分配，再更新​

2. 中位数的两种情况​

3. 空簇：中心原样保留​

4. 中心变化量​

5. inertia 用最终结果算​

6. 输出格式​

完整代码实现​

NumPy 版本​

示例推演​

样例 1：k=1，中心被中位数拉到 (4,5)​

样例 2：k=2，中途出现距离平局​

复杂度分析​

易错点总结​

1. 平局必须取编号最小的簇​

2. 偶数个样本的中位数是中间两项的平均值​

3. 空簇的中心保持不变​

4. 变化量是所有坐标差的总和​

5. 输出的是“先分配、后更新”的同一轮​

6. inertia 要用最终中心和最终分配​

7. 停止条件用严格小于，同时保留迭代上限​

8. 输出浮点格式​

扩展思考​

相关题目​

自测​

题目描述

输入格式

输出格式

示例

示例 1

示例 2

解题思路

第一步：理解问题本质

第二步：暴力解法：每轮全量重算

第三步：优化解法：逐维累加 + 提前剪枝

第四步：完整实现细节

1. 轮次的顺序：先分配，再更新

2. 中位数的两种情况

3. 空簇：中心原样保留

4. 中心变化量

5. inertia 用最终结果算

6. 输出格式

完整代码实现

NumPy 版本

示例推演

样例 1：k=1，中心被中位数拉到 (4,5)

样例 2：k=2，中途出现距离平局

复杂度分析

易错点总结

1. 平局必须取编号最小的簇

2. 偶数个样本的中位数是中间两项的平均值

3. 空簇的中心保持不变

4. 变化量是所有坐标差的总和

5. 输出的是“先分配、后更新”的同一轮

6. inertia 要用最终中心和最终分配

7. 停止条件用严格小于，同时保留迭代上限

8. 输出浮点格式

扩展思考

相关题目

自测