解题思路

1. 整体算法

本题本质是一个带容量约束的 KMeans 聚类 + 新样本最近中心归属问题：

1. 已有 N 个客户，每个是 M 维非负整数特征；
2. 需要分成 K 个簇，并且每个簇人数尽量均衡（容量上限提前固定）；
3. 聚类过程类似 KMeans：

题目内容

某大型企业在运营智能营销平台，需对数干位老客户根据购买偏好数据进行自动化人群分群，以便实现高度针对性的商品推荐和精准推广。然而公司规定每个群组容量需尽可能均衡，避免资源失衡。因此，你需要帮平台开发自动化分群与新用户智能归属方案，具体需求如下：

1.采用 $KMeans$ 变种聚类，将所有客户分为 $K$ 个群组，且保证每组人数相等或只相差 $1$ 。

2.当人数无法均分时，将多出来的客户依次分配给聚类中心编号更小的组，确保分配唯一。

3.对于新客户数据，利用最终分群中心点，确定其最合适归属的群组。

具体描述

1.客户输入：有 $N$ 位已注册客户，每位客户的购买习惯由 $M$ 个正整数特征描述。

2.分群个数：分为 $K$ 个群组 $(2≤K≤min(20,N))$ 。

3.初始聚类中心：为输入前 $K$ 个客户的数据。

4.聚类算法流程

• 每一轮分配，依次处理每个客户(客户编号从小到大，即输入顺序)。

• 对于每个客户，计算其到每个中心的欧几里得距离(如有多个中心距离同为最小，选中心编号更小者)。

• 客户被分配到距离自己最近且该组未满规定容量的中心;若容量已满，则分配给下一个最近、编号更小的可收组。

• 群组容量分配规则为：每组分配人数为 $\lfloor N / K\rfloor \text { 或「N/K }\rceil$ ，多出的依次分配给编号较小的中心组；例如 $N=11,K=3$，则各组容量为 $[4,4,3]$ 。

• 每一轮分配结束后，更新聚类中心为各自组内所有成员特征均值（向下取整）。

• 若所有客户分配及聚类中心均未发生变化，则算法终止。

5.输出中心排序：最终输出 $K$ 个中心点的特征，按字典序升序排列

6.新用户归属：给定新客户的特征后，判定其归属到与其距离最近的聚类中心(如距离相等，优先字典序最小的中心)，输出其中心编号(排序后中心中的序号，从 $1$ 开始)。

输入描述

输入格式

• 第 $1$ 行：$N$ $M$ $K$ (空格分隔)

• 第 $2$ ~ $N+1$ 行：每行 $M$ 个非负整数，表示一个客户的特征

• 第 $N+2$ 行：$M$ 个非负整数，为新客户的特征

输入参数范围

• $2 ≤K ≤ min(20, N)$
• $1≤N ≤2000$
• $1≤M≤10$
• $0≤$ 特征值 $≤10^4$

输出描述

输出格式

• 前 $K$ 行：每行 $M$ 个整数，表示聚类中心的特征，按字典序升序排列
• 第 $K+1$ 行：新客户归属的中心编号(按字典序排序后的位置，$1$ 为首位)

样例1

输入

4 1 2
0
10
0
10
5

输出

0
10
1

说明

• 聚类目标人数为 $[1,1]$，前两组各 $1$ 人。
• 按题算法唯一执行，中心结果唯一。
• 新客户同时与多个中心点等距离，字典序优先，分到第一组。

样例2

输入

8 2 3
10 10
12 9
11 11
100 100
102 99
97 98
50 51
53 49
45 46

输出

11 10
51 50
99 99
2

说明

• 聚类目标人数为 $[3,3,2]$ ，前两组各 $3$ 人，最后 $1$ 组 $2$ 人。

• 按题算法唯一执行，中心结果唯一。

• 新客户 $[45$ $46]$ 归属中间分组，输出 $2$ 。

提示

1.欧几里得距离(Euclidean distance)

• 对于两个 $M$ 维特征的客户 $A$ 和 $B(A=[a_1,a_2,…,a_M ]，B=[b_1,b_2,…,b_M ])$，它们之间的欧几里得距离定义为：$\sqrt{\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}+\cdots+\left(a_{M}-b_{M}\right)^{2}}$

• 建议先计算平方和，再进行平方根(或用于距离大小比较时可直接用平方和，省略开方，顺序不会影响)。

2.均衡分组(Balanced partitioning)

• 若 $N$ 个客户分到 $K$ 组，原则上每组应有 $q=\lfloor N / K\rfloor$人。若 $N$ 不能被 $K$ 整除，则有 $(N$ $mod$ $k)$ 个组会多一人。多出的名额分配给编号较小的分组。

3.字典序(Lexicographical order)

• 多维特征排序时，先比较第 $1$ 维，若相同比第 $2$ 维，依此类推。例如：$[2,3,4]< [2,4,1]< [5,0,0]$ 。

4.唯一性规则说明

• 每个客户依次(输入顺序)分配到当前距离自己最近、且该组人数没到上限的中心，如有多个距离同为最小，选择中心编号最小(即输入时编号更小)的中心。

• 分组人数严格按照上面的第二点分配，保证每组人数最多相差 $1$ ，且人数多的始终是中心编号更小的组。

5.新客户KNN归属

• 将新客户特征与所有最终中心比距离，归属最近中心的分组。

• 若距离有多个中心同为最小，分到字典序最小的中心