页面加载中…
AI001. 多维样本聚类器
中等通过率 60% · 提交 5 · 通过 3
华为 AI 岗K-Means浮点数模拟
算法机考高频题型改编 · 聚焦「华为 AI 岗 / K-Means」 · 难度：中等
给定 n 个 d 维样本、k 个初始聚类中心和迭代次数 t。每轮先按欧氏距离平方分配样本，距离差不超过 1e-9 时选择编号更小的中心；再用簇内均值更新中心，空簇沿用旧中心。完成固定 t 轮后输出全部中心。
这类题属于算法机考高频题型中「华为 AI 岗 / K-Means」方向的高频题型，通常考察对「华为 AI 岗 / K-Means」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
输入描述
第一行输入四个整数 n d k t。接下来 k 行，每行 d 个整数，表示初始聚类中心。随后 n 行，每行 d 个整数，表示一个样本。
输出描述
输出 k 行，每行 d 个保留两位小数的实数，表示最终聚类中心。绝对值小于 0.0005 时输出 0.00。
示例
示例 1
输入示例
4 2 2 2 0 0 8 8 1 1 2 2 8 9 9 8
输出示例
1.50 1.50 8.50 8.50
说明：
两轮后两个簇分别稳定在左下和右上。
示例 2
输入示例
3 2 2 0 -3 4 7 -2 0 0 1 1 2 2
输出示例
-3.00 4.00 7.00 -2.00
说明：
迭代次数为 0，直接输出初始中心。
时间限制 3000 ms · 内存限制 256 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
⚠️ 这道题的坑 · 易错点与反直觉
这些是真正决定能不能 AC、但通用题解里常被略过的点。
- 一轮内必须先把全部样本分配完，再统一更新中心——边分配边更新会让后面的样本看到「半新」的中心
- 空簇沿用旧中心，不是清零也不是报错
- 距离差在 1e-9 内算并列，取编号更小的中心；条件要写成 dist < best - 1e-9
- -0.00 会挂逐字节比对：绝对值小于 0.0005 时输出 0.00
解题思路
考点定位
K-Means 的完整推理模拟：固定轮数下反复执行「分配 → 更新」两个动作。判题不考收敛判断，考的是把三条规则一字不差地写进代码——并列怎么办、空簇怎么办、浮点怎么输出。多数 WA 都死在规则细节而非算法本身。
一轮到底发生了什么
每一轮分两步，顺序不能乱：
1. 分配：对每个样本，计算它到全部 k 个中心的平方欧氏距离（不开方，省一步也避免精度问题），取距离最小的中心。 2. 更新：所有样本分配完之后，才统一用每个簇的均值替换中心。
最容易写错的是把两步搅在一起：一边分配一边改中心，前面样本的分配结果会影响后面样本看到的中心。正确写法是先把本轮全部分配结果存下来，再一次性更新。
三条规则逐个点破
并列取小编号：两个中心的距离差不超过 1e-9 时视作并列，保留编号更小的中心。实现上按编号从小到大遍历，只有 dist < best - 1e-9 才更新 best，天然满足规则。写成 dist < best 看似能过样例，遇到构造的并列用例就翻车。
空簇沿用旧中心：某一轮如果一个中心没分到任何样本，均值无从算起，规则是这个中心保持原值不动。写代码时对每个簇先数样本数，为 0 就跳过更新。
负零钳制：输出保留两位小数，绝对值小于 0.0005 时输出 0.00。浮点均值可能算出 -0.0004 这类值，直接格式化会打出 -0.00，判题逐字节比对必挂。先判绝对值再格式化。
实现步骤
for _ in range(t):
assign = [[] for _ in range(k)] # 本轮各簇的样本
for x in samples:
best, bid = float("inf"), -1
for j, c in enumerate(centers):
d = sum((xi - ci) ** 2 for xi, ci in zip(x, c))
if d < best - 1e-9:
best, bid = d, j
assign[bid].append(x)
for j in range(k):
if assign[j]: # 空簇沿用旧中心
m = len(assign[j])
centers[j] = [sum(col) / m for col in zip(*assign[j])]t 可能为 0：一轮都不跑，直接把初始中心按格式输出，读入和输出的代码路径也要经得起这一档。
复杂度
时间 O(t·n·k·d)，空间 O(n·d + k·d)。规模内纯循环稳过。
易错点清单
- 一轮内边分配边更新中心（顺序错误）。
- 并列判断少了 1e-9 容差，或容差方向写反。
- 空簇直接除以 0，或者把空簇中心清零。
-0.00未钳制；两位小数格式化用错。- t=0 的档位没走通输出路径。
一个一轮的微型走查
拿一个自含的一维小例感受节奏：中心为 0 和 10，样本为 1、2、9。分配步：1 和 2 离中心 0 更近（距离 1、4 对 81、64），9 离中心 10 更近。更新步：第一个簇均值 (1+2)/2 = 1.5，第二个簇均值 9。一轮结束，中心变成 1.5 和 9——两步之间没有任何交叉：分配全程用的是 0 和 10，更新一次性完成。把这个节奏放大到 d 维、k 个中心、t 轮，就是完整实现。
参考代码
# 固定轮数 K-Means 模拟:每轮先把全部样本按平方距离分配(并列取编号小的中心),再统一用簇均值更新,空簇沿用旧中心。
# 输出保留两位小数,绝对值小于 0.0005 输出 0.00,注意负零钳制。
import sys
EPS = 1e-9
def solve() -> None:
tokens = sys.stdin.buffer.read().split()
if not tokens:
return
it = iter(tokens)
n = int(next(it))
d = int(next(it))
k = int(next(it))
rounds = int(next(it))
centers = [[float(next(it)) for _ in range(d)] for _ in range(k)]
points = [[float(next(it)) for _ in range(d)] for _ in range(n)]
for _ in range(rounds):
sums = [[0.0] * d for _ in range(k)]
counts = [0] * k
for point in points:
best = 0
best_dist = sum((point[j] - centers[0][j]) ** 2 for j in range(d))
for c in range(1, k):
dist = sum((point[j] - centers[c][j]) ** 2 for j in range(d))
if dist < best_dist - EPS:
best = c
best_dist = dist
counts[best] += 1
for j in range(d):
sums[best][j] += point[j]
next_centers = [row[:] for row in centers]
for c in range(k):
if counts[c] == 0:
continue
for j in range(d):
next_centers[c][j] = sums[c][j] / counts[c]
centers = next_centers
lines = []
for row in centers:
values = []
for value in row:
if abs(value) < 0.0005:
value = 0.0
values.append(f"{value:.2f}")
lines.append(" ".join(values))
sys.stdout.write("\n".join(lines) + "\n")
if __name__ == "__main__":
solve()
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
