解题思路

本题本质是一个典型的 KMeans 聚类 问题：给定每个终端的 4 维特征（包间隔时长、连接持续时长、漫游前信号强度、漫游后信号强度），将这些终端划分成 K 个簇，每个簇对应一种终端款型，最后输出每个簇中终端数量（从小到大排序）。

1. KMeans 算法回顾与本题设定

KMeans 的标准流程为：

1. 初始化质心

   • 从数据集中选择 K 个点作为初始质心。
   • 本题明确要求：初始化质心使用数据集中前 k 个点。

2. 分配（Assignment）

   • 对每个样本点，计算其到所有质心的距离，将该点分配给最近的质心所属的簇。

   • 距离定义为 4 维欧氏距离：

     $$d(x,y)=\sqrt{\sum_{i=1}^4 (x_i-y_i)^2}$$

   • 实现时可直接用 平方距离（去掉根号），比较大小结果相同，少一次 sqrt，更高效：

     $$d^2(x,y)=\sum_{i=1}^4 (x_i-y_i)^2$$

3. 更新质心（Update）

   • 对每个簇，计算簇内所有样本的 4 维特征均值，将其作为新的质心：

     $$\mu_j = \frac{1}{|C_j|}\sum_{x \in C_j} x$$

4. 迭代与收敛条件

   • 重复“分配 + 更新”步骤，直到：

     • 质心移动距离足够小（本题要求：质心移动值 < $10^{-8}$），或
     • 达到给定的最大迭代次数 n。

   • 具体实现中，我们可以对每个质心计算新旧质心的平方距离，取所有质心中 最大移动量：

     $$\text{move}_j = \sum_{i=1}^4(\mu_{j,i}^{\text{new}} - \mu_{j,i}^{\text{old}})^2 $$

     若所有质心的最大移动量 < $10^{-8}$，则认为收敛。

5. 空簇问题的处理

   • 理论上，KMeans 可能会出现某个簇为空的情况。

   • 本题说明中给出：数据集中 默认 K 类终端都存在。 但在迭代过程中仍有极小概率产生空簇，因此实现时可以做一个稳健处理：

     • 若某个簇在当前分配中没有任何点（数量为 0），则 保持该簇的质心不变，避免除零错误。

6. 最终输出

   • 算法停止后，我们已经有每个终端的簇归属，统计每个簇内终端数量，得到长度为 K 的数组。
   • 按题意要求，将这 K 个数量 从小到大排序，用空格分隔输出。

2. 实现要点

1. 读入数据

   • 第 1 行：k m n

     • k：簇的个数（终端款型数）
     • m：样本个数（终端数）
     • n：最大迭代次数

   • 接下来 m 行，每行 4 个浮点数，表示该终端的 4 维特征（已归一化，保留两位小数）。

2. 数据结构设计

   • points[m][4]：保存所有终端的 4 维特征。
   • centroids[k][4]：当前 k 个质心。
   • assign[m]：每个终端所属的簇编号（0 ~ k-1）。
   • clusterSize[k]：每个簇中点的个数。
   • sum[k][4]：每个簇中各维度特征之和，用于计算新质心。

3. 初始化

   • centroids[i] = points[i] 对于 i ∈ [0, k-1]。

4. 每次迭代流程

   • 将 clusterSize 和 sum 清零。

   • 遍历每个点：

     • 依次计算该点到每个质心的 平方距离，找到最小值对应的簇 j。
     • assign[i] = j，clusterSize[j]++，并将当前点特征累加到 sum[j] 中。

   • 使用 sum 和 clusterSize 更新每个质心：

     • 若 clusterSize[j] > 0：

       • 新质心 = sum[j][d] / clusterSize[j]。

     • 若 clusterSize[j] == 0：

       • 保持原质心不变。

   • 同时在更新时，计算新旧质心之间的最大移动距离，用于判断收敛。

5. 结束后统计结果

   • 上一轮分配的 clusterSize 即为最终每个簇的点数。
   • 将 clusterSize 拷贝到数组，排序，然后输出。

代码实现

Python 实现

import sys
import math

# 计算两点之间的平方欧氏距离（4 维）
def dist2(a, b):
    s = 0.0
    for i in range(4):
        diff = a[i] - b[i]
        s += diff * diff
    return s

def kmeans(points, k, max_iter):
    m = len(points)
    # 初始化质心：前 k 个点
    centroids = [points[i][:] for i in range(k)]
    assign = [0] * m
    cluster_size = [0] * k

    for _ in range(max_iter):
        # 分配步骤
        for j in range(k):
            cluster_size[j] = 0
        sums = [[0.0] * 4 for _ in range(k)]

        for i in range(m):
            # 找到最近质心
            best_idx = 0
            best_dist = dist2(points[i], centroids[0])
            for j in range(1, k):
                d = dist2(points[i], centroids[j])
                if d < best_dist:
                    best_dist = d
                    best_idx = j
            assign[i] = best_idx
            cluster_size[best_idx] += 1
            # 累加簇内点特征
            for t in range(4):
                sums[best_idx][t] += points[i][t]

        # 更新质心
        max_move = 0.0
        for j in range(k):
            if cluster_size[j] > 0:
                new_centroid = [sums[j][t] / cluster_size[j] for t in range(4)]
            else:
                # 若该簇为空，保持旧质心不变
                new_centroid = centroids[j][:]

            # 计算质心移动距离（平方）
            move = dist2(centroids[j], new_centroid)
            if move > max_move:
                max_move = move
            centroids[j] = new_centroid

        # 收敛判断：最大质心移动小于 1e-8
        if max_move < 1e-8:
            break

    # cluster_size 即为各簇最终数量
    return cluster_size

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    k = int(data[0])
    m = int(data[1])
    max_iter = int(data[2])

    points = []
    idx = 3
    for _ in range(m):
        # 依次读入 4 个浮点数
        row = list(map(float, data[idx:idx+4]))
        idx += 4
        points.append(row)

    sizes = kmeans(points, k, max_iter)
    sizes.sort()
    print(" ".join(str(x) for x in sizes))

if __name__ == "__main__":
    main()

Java 实现

import java.util.*;

// ACM 模式，主类名必须为 Main
public class Main {

    // 计算两个 4 维点的平方欧氏距离
    private static double dist2(double[] a, double[] b) {
        double s = 0.0;
        for (int i = 0; i < 4; i++) {
            double diff = a[i] - b[i];
            s += diff * diff;
        }
        return s;
    }

    // KMeans 聚类主函数
    private static int[] kmeans(double[][] points, int k, int maxIter) {
        int m = points.length;
        double[][] centroids = new double[k][4];
        int[] assign = new int[m];
        int[] clusterSize = new int[k];

        // 初始化质心：前 k 个点
        for (int i = 0; i < k; i++) {
            for (int d = 0; d < 4; d++) {
                centroids[i][d] = points[i][d];
            }
        }

        // 迭代
        for (int it = 0; it < maxIter; it++) {
            // 清空簇大小
            for (int j = 0; j < k; j++) {
                clusterSize[j] = 0;
            }
            // sums 用来累加每个簇的特征和
            double[][] sums = new double[k][4];

            // 分配每个点到最近的质心
            for (int i = 0; i < m; i++) {
                double bestDist = dist2(points[i], centroids[0]);
                int bestIdx = 0;
                for (int j = 1; j < k; j++) {
                    double d = dist2(points[i], centroids[j]);
                    if (d < bestDist) {
                        bestDist = d;
                        bestIdx = j;
                    }
                }
                assign[i] = bestIdx;
                clusterSize[bestIdx]++;
                for (int d = 0; d < 4; d++) {
                    sums[bestIdx][d] += points[i][d];
                }
            }

            // 更新质心并计算最大移动距离
            double maxMove = 0.0;
            for (int j = 0; j < k; j++) {
                double[] newCentroid = new double[4];
                if (clusterSize[j] > 0) {
                    for (int d = 0; d < 4; d++) {
                        newCentroid[d] = sums[j][d] / clusterSize[j];
                    }
                } else {
                    // 若簇为空，质心保持不变
                    for (int d = 0; d < 4; d++) {
                        newCentroid[d] = centroids[j][d];
                    }
                }
                double move = dist2(centroids[j], newCentroid);
                if (move > maxMove) {
                    maxMove = move;
                }
                centroids[j] = newCentroid;
            }

            // 收敛条件
            if (maxMove < 1e-8) {
                break;
            }
        }

        // clusterSize 即为每个簇的终端数量
        return clusterSize;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNext()) {
            return;
        }
        int k = sc.nextInt();
        int m = sc.nextInt();
        int maxIter = sc.nextInt();

        double[][] points = new double[m][4];
        for (int i = 0; i < m; i++) {
            for (int d = 0; d < 4; d++) {
                points[i][d] = sc.nextDouble();
            }
        }

        int[] sizes = kmeans(points, k, maxIter);
        Arrays.sort(sizes);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < sizes.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(sizes[i]);
        }
        System.out.println(sb.toString());
    }
}

C++ 实现

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

// 计算两个 4 维点的平方欧氏距离
double dist2(const array<double, 4>& a, const array<double, 4>& b) {
    double s = 0.0;
    for (int i = 0; i < 4; ++i) {
        double diff = a[i] - b[i];
        s += diff * diff;
    }
    return s;
}

// KMeans 聚类主函数
vector<int> kmeans(const vector<array<double, 4>>& points, int k, int maxIter) {
    int m = (int)points.size();
    vector<array<double, 4>> centroids(k);
    vector<int> assign(m, 0);
    vector<int> clusterSize(k, 0);

    // 初始化质心：前 k 个点
    for (int i = 0; i < k; ++i) {
        centroids[i] = points[i];
    }

    for (int it = 0; it < maxIter; ++it) {
        // 清空簇信息
        fill(clusterSize.begin(), clusterSize.end(), 0);
        vector<array<double, 4>> sums(k);
        for (int j = 0; j < k; ++j) {
            for (int d = 0; d < 4; ++d) {
                sums[j][d] = 0.0;
            }
        }

        // 分配每个点到最近质心
        for (int i = 0; i < m; ++i) {
            double bestDist = dist2(points[i], centroids[0]);
            int bestIdx = 0;
            for (int j = 1; j < k; ++j) {
                double d = dist2(points[i], centroids[j]);
                if (d < bestDist) {
                    bestDist = d;
                    bestIdx = j;
                }
            }
            assign[i] = bestIdx;
            clusterSize[bestIdx]++;
            for (int d = 0; d < 4; ++d) {
                sums[bestIdx][d] += points[i][d];
            }
        }

        // 更新质心并计算最大移动量
        double maxMove = 0.0;
        for (int j = 0; j < k; ++j) {
            array<double, 4> newCentroid;
            if (clusterSize[j] > 0) {
                for (int d = 0; d < 4; ++d) {
                    newCentroid[d] = sums[j][d] / clusterSize[j];
                }
            } else {
                // 若簇为空，质心保持不变
                newCentroid = centroids[j];
            }
            double move = dist2(centroids[j], newCentroid);
            if (move > maxMove) {
                maxMove = move;
            }
            centroids[j] = newCentroid;
        }

        // 收敛判断
        if (maxMove < 1e-8) {
            break;
        }
    }

    // clusterSize 即为最终每个簇的数量
    return clusterSize;
}

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

    int k, m, maxIter;
    if (!(cin >> k >> m >> maxIter)) {
        return 0;
    }

    vector<array<double, 4>> points(m);
    for (int i = 0; i < m; ++i) {
        for (int d = 0; d < 4; ++d) {
            cin >> points[i][d];
        }
    }

    vector<int> sizes = kmeans(points, k, maxIter);
    sort(sizes.begin(), sizes.end());
    for (int i = 0; i < (int)sizes.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << sizes[i];
    }
    cout << '\n';

    return 0;
}

题目内容

某部门需要对终端的漫游业务体验进行保障，不同的终端对于网络的配置要求不同。现在需要通过终端的网络流量等特征，识别该终端的型号是什么。

通过包间隔时长、连接持续时长、漫游前信号强度及漫游后信号强度 $4$ 个特征，对终端的型号进行聚类。已知终端型号类别为 $K$ 类，采用 $Kmeans$ 算法进行聚类，识别终端类型，并输出各类型终端数量。

$Kmeans$ 算法说明:

初始化: $k$ 个初始质心

分配:将每个数据点分配到距离最近的质心，形成 $k$ 个簇。其中距离需要根据数据类型选择上文给定的度量方式

更新:用簇内所有点的均值，重新计算每个簇的质心

迭代:重复步骤 $2$ 和 $3$ ，直到质心不再发生变化(质心移动值小于 $10^{-8}$ )或达到最大迭代次数

本题说明:

1、给定数据集中，默认 $K$ 类终端都存在，不存在某款型终端个数为 $0$ 的场景;

2、为消除不同特征权重问题，给出数据均已做好归一化处理，并保留两位小数;

3、为消除随机性，初始 $k$ 个质心统一采用给定数据集前 $k$ 个点;

4、距离函数定义为: $d_{x, y}=\sqrt{\sum_{k=1}^{4}\left(x_{k}-y_{k}\right)^{2}}$

输入描述

第 $1$ 行: $k$ $m$ $n$ : $k$ 代表终端款型聚类个数，$m$ 代表终端数量，$n$ 代表迭代次数;

第 $2$ 行 ~ 第 $m+1$ 行:每一行 $4$ 列，分别代表某个终端的包间隔时长、连接持续时长、漫游前信号强度及漫游后信号强度 $4$ 个变量

输出描述

输出 $k$ 款终端数量，从小到大排序。

样例1

输入

3 20 1000
0.11 0.79 0.68 0.97
1.0 0.8 0.13 0.33
0.27 0.02 0.5 0.46
0.83 0.29 0.23 0.75
0.97 0.08 0.84 0.55
0.29 0.71 0.17 0.83
0.03 0.6 0.88 0.28
0.24 0.26 0.82 0.03
0.96 0.12 0.82 0.36
0.13 0.12 0.86 0.44
0.23 0.7 0.35 0.06
0.42 0.49 0.67 0.84
0.8 0.49 0.47 0.7
0.68 0.03 0.11 0.07
0.77 0.19 0.95 0.44
0.25 0.12 0.98 0.04
0.7 0.11 0.53 0.3
0.73 0.67 0.46 0.96
0.11 0.31 0.91 0.57
0.43 0.61 0.13 0.1

输出

4 6 10

说明

输入: $20$ 个终端，其中包含 $3$ 种款式，用 $Kmeans$ 算法最高选代 $1000$ 次计算每款终端个数

输出: $3$ 款终端数量从小到大排序为 $4$ $6$ $10$

样例2

输入

4 32 800
0.73 0.96 0.2 0.53
0.01 0.19 0.42 0.46
0.27 0.24 0.87 0.8
0.97 0.77 0.42 0.04
0.41 0.69 0.96 0.56
0.27 0.4 0.56 0.56
0.28 0.04 0.74 0.82
0.17 0.2 0.95 0.1
0.2 0.1 0.14 0.93
0.86 0.59 0.42 0.52
0.35 0.77 0.37 0.08
0.52 0.48 0.16 0.56
0.59 0.97 0.21 0.05
0.67 0.94 0.28 0.08
0.09 0.65 0.55 1.0
0.77 0.14 0.35 0.01
0.02 0.18 0.72 0.26
0.71 0.78 0.86 0.11
0.54 0.02 0.75 0.2
0.15 0.76 0.59 0.23
0.71 0.66 0.43 0.32
0.17 0.57 0.53 0.42
0.04 0.34 0.66 0.28
0.79 0.14 0.11 0.6
0.04 0.48 0.05 0.04
0.62 0.43 0.28 0.6
0.47 0.13 0.35 0.17
0.9 0.82 0.97 0.71
0.99 0.53 0.24 0.56
0.83 0.44 0.7 0.4
0.71 0.45 0.64 0.53
0.6 0.54 0.86 0.11

输出

6 8 9 9

说明

输入: $32$ 个终端，其中包含 $4$ 种款式，用 $Kmeans$ 算法最高迭代 $800$ 次计算每款终端个数

输出: $4$ 款终端数量从小到大排序为 $6899$