解题思路

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

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

KMeans 的标准流程为：

1. 初始化质心

题目内容

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

通过包间隔时长、连接持续时长、漫游前信号强度及漫游后信号强度 $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$