解题思路

1. 整体算法

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

1. 已有 N 个客户，每个是 M 维非负整数特征；

2. 需要分成 K 个簇，并且每个簇人数尽量均衡（容量上限提前固定）；

3. 聚类过程类似 KMeans：

   • 用前 K 个样本作为初始中心；
   • 反复执行「按当前中心分配 → 重新计算中心」直到收敛；

4. 聚类完成后：

   • 将 K 个中心按字典序排序并输出；
   • 对新用户，用“最近中心 + 字典序优先”来决定归属中心，并输出其在排序后的位置。

这里的关键在于：分配阶段的容量约束和选择规则与普通 KMeans 不同。

2. 容量（目标人数）计算

先计算每个簇最大容量（题目保证最终都是满的）：

• 设

  • q = N // K（每组至少 q 人）
  • r = N % K（前 r 个组多一个人）

• 则组 0..K-1 的目标容量为：

  • 若 i < r，容量为 q + 1
  • 否则容量为 q

例如：N = 11, K = 3 → q = 3, r = 2 → 容量 [4, 4, 3]。

这样就保证：

• 每组人数只差 0 或 1；
• 人数更多的一定是编号更小的组（前面的组先拿到额外名额）。

3. 聚类迭代过程（变种 KMeans）

1. 初始化中心

   • 直接把前 K 个客户的特征当作初始中心 centers[0..K-1]。

2. 一次分配轮次（Assignment Step）

   依次处理每个客户 i = 0..N-1：

   • 计算它到每个中心 k 的欧氏距离的平方（不必开根号，比较大小即可）：

     $$dist^2 = \sum_{d=0}^{M-1} (x_{i,d} - center_{k,d})^2$$

   • 对所有簇 (k) 按 (距离, k) 升序排序（先比距离，再比簇编号）；

   • 从排序后的簇中，找到第一个未达容量上限的簇，把客户 i 分给它：

     • 如果最优簇已满，则尝试下一个距离最近的簇；
     • 总会找到一个，因为整体容量之和就是 N。

   这样就满足了：

   • 优先选择距离最近的中心；
   • 距离相等时，优先中心编号更小；
   • 容量被严格限制在预先计算好的上限。

3. 更新中心（Update Step）

   分配完成后，对每个簇 k：

   • 累加该簇内所有客户在各维度的特征和；
   • 再对每维特征做整数平均（向下取整）：$$center_{k,d} = \left\lfloor \frac{\sum x_{i,d}}{\text{簇内人数}} \right\rfloor$$

4. 终止条件（收敛）

   • 如果本轮分配得到的 assign[] 与上一轮完全一样，
   • 且本轮计算出的 centers[][] 也与上一轮完全一样，
   • 则认为算法收敛，终止循环。
   • 否则继续下一轮。

   注：状态空间有限（中心取值有限、分配方式有限），最终一定会收敛。

4. 输出中心 + 新用户归属

1. 中心排序 收敛后得到最终 K 个中心。 按字典序升序排序：

   • 先比第 1 维，不同则小者在前；
   • 相同再比第 2 维，以此类推。

   输出排序后的 K 行中心向量。

2. 新用户归属（KNN 到中心）

   用排序后的中心数组 sorted_centers 对新用户进行一次简单的「最近中心判断」：

   • 对每个中心 c，计算新用户与其的欧氏距离平方；

   • 选择距离最小的中心；

   • 如果有多个中心距离相等，则优先选择字典序更小的中心。

     • 因为我们已经按照字典序排序，所以在遍历中“先出现”的中心自然就是字典序更小的；

   • 输出该中心在排序数组中的位置（1 开始编号）。

代码实现

Python

import sys
from math import inf

# 计算两点间欧氏距离的平方
def dist2(a, b):
    s = 0
    for x, y in zip(a, b):
        diff = x - y
        s += diff * diff
    return s

def balanced_kmeans(customers, K):
    N = len(customers)
    M = len(customers[0])

    # 计算每个簇的目标容量
    base = N // K
    rem = N % K
    capacity = [base + (1 if i < rem else 0) for i in range(K)]

    # 初始中心：前 K 个客户
    centers = [customers[i][:] for i in range(K)]

    # 初始分配，全部设为 -1
    assign = [-1] * N

    while True:
        # 新一轮分配
        new_assign = [-1] * N
        sizes = [0] * K

        # 按客户编号从小到大分配
        for i in range(N):
            point = customers[i]

            # 计算到每个中心的距离
            dist_list = []
            for k in range(K):
                d2 = dist2(point, centers[k])
                dist_list.append((d2, k))

            # 按 (距离, 中心编号) 排序
            dist_list.sort()

            # 找到第一个未满容量的中心
            for _, k in dist_list:
                if sizes[k] < capacity[k]:
                    new_assign[i] = k
                    sizes[k] += 1
                    break

        # 根据新分配结果更新中心
        new_centers = [[0] * M for _ in range(K)]
        counts = [0] * K
        for i in range(N):
            c = new_assign[i]
            counts[c] += 1
            for d in range(M):
                new_centers[c][d] += customers[i][d]

        for k in range(K):
            # 每个簇一定有容量，所以 counts[k] > 0
            for d in range(M):
                new_centers[k][d] //= counts[k]

        # 判断是否收敛（分配和中心都不变）
        if new_assign == assign and new_centers == centers:
            centers = new_centers
            assign = new_assign
            break
        else:
            centers = new_centers
            assign = new_assign

    return centers

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))

    customers = []
    for _ in range(N):
        point = [int(next(it)) for _ in range(M)]
        customers.append(point)

    new_customer = [int(next(it)) for _ in range(M)]

    # 执行均衡 KMeans
    centers = balanced_kmeans(customers, K)

    # 按字典序排序中心
    centers.sort()

    # 输出中心
    out_lines = []
    for c in centers:
        out_lines.append(" ".join(str(x) for x in c))

    # 新用户归属：最近中心，距离相等时字典序更小（排序后自然满足）
    best_idx = 0
    best_dist = dist2(new_customer, centers[0])
    for i in range(1, K):
        d2 = dist2(new_customer, centers[i])
        if d2 < best_dist:
            best_dist = d2
            best_idx = i
        # 若距离相等，由于中心已按字典序排序，保留原来的较小下标即可

    out_lines.append(str(best_idx + 1))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    // 计算两点欧氏距离的平方
    public static long dist2(int[] a, int[] b) {
        long s = 0;
        for (int i = 0; i < a.length; i++) {
            long diff = (long)a[i] - (long)b[i];
            s += diff * diff;
        }
        return s;
    }

    // 均衡 KMeans 主过程
    public static int[][] balancedKMeans(int[][] customers, int K) {
        int N = customers.length;
        int M = customers[0].length;

        // 计算容量
        int base = N / K;
        int rem = N % K;
        int[] capacity = new int[K];
        for (int i = 0; i < K; i++) {
            capacity[i] = base + (i < rem ? 1 : 0);
        }

        // 初始中心：前 K 个客户
        int[][] centers = new int[K][M];
        for (int k = 0; k < K; k++) {
            for (int d = 0; d < M; d++) {
                centers[k][d] = customers[k][d];
            }
        }

        int[] assign = new int[N];
        for (int i = 0; i < N; i++) assign[i] = -1;

        while (true) {
            int[] newAssign = new int[N];
            for (int i = 0; i < N; i++) newAssign[i] = -1;
            int[] sizes = new int[K];

            // 分配每个客户
            for (int i = 0; i < N; i++) {
                int[] point = customers[i];

                long[] dist = new long[K];
                for (int k = 0; k < K; k++) {
                    dist[k] = dist2(point, centers[k]);
                }

                // 根据距离和中心编号选择未满容量的中心
                boolean[] used = new boolean[K];
                while (true) {
                    int best = -1;
                    for (int k = 0; k < K; k++) {
                        if (used[k]) continue;
                        if (best == -1 || dist[k] < dist[best] ||
                                (dist[k] == dist[best] && k < best)) {
                            best = k;
                        }
                    }
                    used[best] = true;
                    if (sizes[best] < capacity[best]) {
                        newAssign[i] = best;
                        sizes[best]++;
                        break;
                    }
                    // 如果这个中心已满，则继续找下一个最近的
                }
            }

            // 根据新分配更新中心
            int[][] newCenters = new int[K][M];
            int[] counts = new int[K];
            for (int i = 0; i < N; i++) {
                int c = newAssign[i];
                counts[c]++;
                for (int d = 0; d < M; d++) {
                    newCenters[c][d] += customers[i][d];
                }
            }

            for (int k = 0; k < K; k++) {
                for (int d = 0; d < M; d++) {
                    newCenters[k][d] /= counts[k];
                }
            }

            // 判断是否收敛
            boolean sameAssign = true;
            for (int i = 0; i < N; i++) {
                if (newAssign[i] != assign[i]) {
                    sameAssign = false;
                    break;
                }
            }

            boolean sameCenter = true;
            for (int k = 0; k < K && sameCenter; k++) {
                for (int d = 0; d < M; d++) {
                    if (newCenters[k][d] != centers[k][d]) {
                        sameCenter = false;
                        break;
                    }
                }
            }

            centers = newCenters;
            assign = newAssign;

            if (sameAssign && sameCenter) {
                break;
            }
        }

        return centers;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String firstLine = br.readLine();
        if (firstLine == null || firstLine.trim().isEmpty()) return;
        String[] parts = firstLine.trim().split("\\s+");
        int N = Integer.parseInt(parts[0]);
        int M = Integer.parseInt(parts[1]);
        int K = Integer.parseInt(parts[2]);

        int[][] customers = new int[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            while (line != null && line.trim().isEmpty()) {
                line = br.readLine();
            }
            String[] arr = line.trim().split("\\s+");
            for (int j = 0; j < M; j++) {
                customers[i][j] = Integer.parseInt(arr[j]);
            }
        }

        int[] newCustomer = new int[M];
        String line = br.readLine();
        while (line != null && line.trim().isEmpty()) {
            line = br.readLine();
        }
        String[] arr = line.trim().split("\\s+");
        for (int j = 0; j < M; j++) {
            newCustomer[j] = Integer.parseInt(arr[j]);
        }

        // 执行均衡 KMeans
        int[][] centers = balancedKMeans(customers, K);

        // 按字典序排序中心
        java.util.Arrays.sort(centers, (a, b) -> {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) return a[i] - b[i];
            }
            return 0;
        });

        StringBuilder sb = new StringBuilder();
        // 输出中心
        for (int k = 0; k < K; k++) {
            for (int d = 0; d < M; d++) {
                if (d > 0) sb.append(' ');
                sb.append(centers[k][d]);
            }
            sb.append('\n');
        }

        // 新用户归属
        long bestDist = dist2(newCustomer, centers[0]);
        int bestIdx = 0;
        for (int i = 1; i < K; i++) {
            long d2 = dist2(newCustomer, centers[i]);
            if (d2 < bestDist) {
                bestDist = d2;
                bestIdx = i;
            }
            // 若距离相等，因排序后字典序递增，保留较小下标即可
        }

        sb.append(bestIdx + 1).append('\n');

        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算两点欧氏距离的平方
long long dist2(const vector<int> &a, const vector<int> &b) {
    long long s = 0;
    for (size_t i = 0; i < a.size(); i++) {
        long long diff = (long long)a[i] - (long long)b[i];
        s += diff * diff;
    }
    return s;
}

// 均衡 KMeans 主过程
vector<vector<int>> balancedKMeans(const vector<vector<int>> &customers, int K) {
    int N = (int)customers.size();
    int M = (int)customers[0].size();

    // 计算容量
    int base = N / K;
    int rem = N % K;
    vector<int> capacity(K);
    for (int i = 0; i < K; i++) {
        capacity[i] = base + (i < rem ? 1 : 0);
    }

    // 初始中心：前 K 个客户
    vector<vector<int>> centers(K, vector<int>(M));
    for (int k = 0; k < K; k++) {
        centers[k] = customers[k];
    }

    vector<int> assign(N, -1);

    while (true) {
        vector<int> newAssign(N, -1);
        vector<int> sizes(K, 0);

        // 分配每个客户
        for (int i = 0; i < N; i++) {
            const vector<int> &point = customers[i];

            vector<long long> dist(K);
            for (int k = 0; k < K; k++) {
                dist[k] = dist2(point, centers[k]);
            }

            vector<bool> used(K, false);
            while (true) {
                int best = -1;
                for (int k = 0; k < K; k++) {
                    if (used[k]) continue;
                    if (best == -1 || dist[k] < dist[best] ||
                        (dist[k] == dist[best] && k < best)) {
                        best = k;
                    }
                }
                used[best] = true;
                if (sizes[best] < capacity[best]) {
                    newAssign[i] = best;
                    sizes[best]++;
                    break;
                }
                // 否则继续找下一个最近且未满的中心
            }
        }

        // 更新中心
        vector<vector<long long>> sum(K, vector<long long>(M, 0));
        vector<int> counts(K, 0);

        for (int i = 0; i < N; i++) {
            int c = newAssign[i];
            counts[c]++;
            for (int d = 0; d < M; d++) {
                sum[c][d] += customers[i][d];
            }
        }

        vector<vector<int>> newCenters(K, vector<int>(M));
        for (int k = 0; k < K; k++) {
            for (int d = 0; d < M; d++) {
                newCenters[k][d] = (int)(sum[k][d] / counts[k]);
            }
        }

        // 判断是否收敛
        bool sameAssign = true;
        for (int i = 0; i < N; i++) {
            if (newAssign[i] != assign[i]) {
                sameAssign = false;
                break;
            }
        }

        bool sameCenter = true;
        for (int k = 0; k < K && sameCenter; k++) {
            for (int d = 0; d < M; d++) {
                if (newCenters[k][d] != centers[k][d]) {
                    sameCenter = false;
                    break;
                }
            }
        }

        centers.swap(newCenters);
        assign.swap(newAssign);

        if (sameAssign && sameCenter) {
            break;
        }
    }

    return centers;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    if (!(cin >> N >> M >> K)) {
        return 0;
    }

    vector<vector<int>> customers(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> customers[i][j];
        }
    }

    vector<int> newCustomer(M);
    for (int j = 0; j < M; j++) {
        cin >> newCustomer[j];
    }

    // 执行均衡 KMeans
    vector<vector<int>> centers = balancedKMeans(customers, K);
    int dim = M;

    // 按字典序排序中心
    sort(centers.begin(), centers.end(), [dim](const vector<int> &a, const vector<int> &b) {
        for (int i = 0; i < dim; i++) {
            if (a[i] != b[i]) return a[i] < b[i];
        }
        return false;
    });

    // 输出中心
    for (int k = 0; k < K; k++) {
        for (int d = 0; d < M; d++) {
            if (d) cout << ' ';
            cout << centers[k][d];
        }
        cout << "\n";
    }

    // 新用户归属
    long long bestDist = dist2(newCustomer, centers[0]);
    int bestIdx = 0;
    for (int i = 1; i < K; i++) {
        long long d2 = dist2(newCustomer, centers[i]);
        if (d2 < bestDist) {
            bestDist = d2;
            bestIdx = i;
        }
        // 若距离相等，排序后字典序小的在前，保留原下标即可
    }

    cout << (bestIdx + 1) << "\n";

    return 0;
}

题目内容

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

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归属

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

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