某电商平台需要把 N 位老客户按其 M 维非负整数特征划分为 K 个群组（2 ≤ K ≤ min(20, N)）。为避免资源倾斜，要求每个群组的容量严格均衡：每组人数为 NK 或 NK+1，多出来的人数依次补给“中心编号较小”的群组。你需要实现一个“按顺序分配 + 均衡容量 + 中心取整”的 KMeans 变体，并用最终的中心点将一个新客户归到最近的中心。 算法规则 1) 初始中心为输入的前 K 位客户的特征。 2) 每一轮分配按客户输入顺序从 1 到 N 顺序处理。对每个客户： 计算其到每个中心的欧氏距离（可用“平方和”比较，无需开方）。 在“尚未满员”的中心里选择距离最小者；若有距离并列，取中心编号更小的。 每个中心的容量固定：前 N%K 个中心容量为 NK+1，其余为 NK。 3) 一轮分配完成后，更新每个中心为该组所有成员的逐维均值向下取整（floor）。 4) 若“本轮的分配结果和中心”与上一轮完全一致，则停止。 5) 输出时先将最终中心按字典序（先比第 1 维，再比第 2 维，依此类推）升序排序；随后给定新客户特征，计算他到“已排序中心”的距离，归到最近的中心；若有并列，选择字典序最小的中心。输出该中心在“排序后列表”中的序号（从 1 开始）。
输入描述:
第 1 行：N M K第 2 ~ N+1 行：每行 M 个非负整数，表示一位老客户的特征第 N+2 行：M 个非负整数，表示新客户的特征


输出描述:
先输出 K 行：排序后的 K 个中心（每行 M 个整数）再输出 1 行：新客户所在中心在排序后列表中的序号（从 1 开始）
示例1

输入

4 1 2
0
10
9
11
8

输出

5
9
2

说明

1.按“容量均衡 + 顺序分配”规则，4 个点分到两组容量各 2：{0,11} 与 {10,9}。  
2.组中心为各组均值下取整：{5,9}，再次分配不变，收敛。  
3.新点 8 到中心 5、9 的距离分别为 9 和 1，选 9，排序后位次为 2。


备注:
可用“平方距离”比较代替真实欧氏距离，顺序不变。均衡容量固定不变：前 (N mod K) 个中心容量为 NK+1，其余为 NK。所有并列均按“编号小字典序小”打破平局。
加载中...