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