1000ms

Difficulty: 6

所属公司 : 华为

时间 :2026年3月4日-AI方向

算法标签>

机器学习算法

解题思路

题目要求在给定初始聚类中心的前提下，按 $KMeans$ 聚类算法迭代更新中心点。

核心流程（重复给定迭代次数 $T$ 轮）：

分配样本：对每个样本点，计算它到每个聚类中心的欧式距离 $( d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} )$ 将样本分配给距离最近的中心（若距离相同，取编号更小的中心即可，代码里自然满足）。
更新中心：对每个簇，把簇内所有样本在三个维度分别求平均，得到新的中心点。
特殊情况：若某个簇本轮没有分到任何样本，则该簇中心保持不变（避免除以 $0$ ）。

最后输出迭代完成后的 $K$ 个中心点，每行 $3$ 个数，保留两位小数（四舍五入）。

复杂度分析

设样本数为 $m$ ，聚类数为 $k$ ，迭代次数为 $T$ 。

时间复杂度：每轮需要对每个样本计算 $k$ 次距离，整体为 $O(T * m * k)$
空间复杂度：存储样本与中心及统计量， $O(m + k)$

代码实现

import sys
from decimal import Decimal, ROUND_HALF_UP

# 题面功能：执行KMeans迭代，返回最终聚类中心
def kmeans_update(centers, points, iters):
    k = len(centers)
    for _ in range(iters):
        # 记录每个簇的三维和与数量
        sumx = [0.0] * k
        sumy = [0.0] * k
        sumz = [0.0] * k
        cnt = [0] * k

        # 1) 分配样本到最近中心
        for (px, py, pz) in points:
            best = 0
            bx, by, bz = centers[0]
            best_dist = (px - bx) ** 2 + (py - by) ** 2 + (pz - bz) ** 2
            for j in range(1, k):
                cx, cy, cz = centers[j]
                d = (px - cx) ** 2 + (py - cy) ** 2 + (pz - cz) ** 2
                if d < best_dist:
                    best_dist = d
                    best = j
            sumx[best] += px
            sumy[best] += py
            sumz[best] += pz
            cnt[best] += 1

        # 2) 更新中心（空簇则保持不变）
        new_centers = []
        for j in range(k):
            if cnt[j] == 0:
                new_centers.append(centers[j])
            else:
                new_centers.append((sumx[j] / cnt[j], sumy[j] / cnt[j], sumz[j] / cnt[j]))
        centers = new_centers
    return centers

def fmt2(x):
    # 输出时按“四舍五入”保留两位小数
    return str(Decimal(str(x)).quantize(Decimal("0.00"), rounding=ROUND_HALF_UP))

def main():
    data = sys.stdin.read().strip().split()
    idx = 0

    k = int(data[idx]); idx += 1
    centers = []
    for _ in range(k):
        x = float(data[idx]); y = float(data[idx + 1]); z = float(data[idx + 2])
        idx += 3
        centers.append((x, y, z))

    iters = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    points = []
    for _ in range(m):
        x = float(data[idx]); y = float(data[idx + 1]); z = float(data[idx + 2])
        idx += 3
        points.append((x, y, z))

    centers = kmeans_update(centers, points, iters)

    out_lines = []
    for (x, y, z) in centers:
        out_lines.append(f"{fmt2(x)} {fmt2(y)} {fmt2(z)}")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

#include <bits/stdc++.h>
using namespace std;
// 题面功能：执行KMeans迭代，返回最终聚类中心
vector<array<double,3>> kmeansUpdate(vector<array<double,3>> centers,
                                    const vector<array<double,3>>& points,
                                    int iters) {
    int k = (int)centers.size();

    for (int t = 0; t < iters; t++) {
        vector<double> sumx(k, 0.0), sumy(k, 0.0), sumz(k, 0.0);
        vector<int> cnt(k, 0);

        // 1) 分配样本到最近中心
        for (auto &p : points) {
            double px = p[0], py = p[1], pz = p[2];

            int best = 0;
            double bx = centers[0][0], by = centers[0][1], bz = centers[0][2];
            double bestDist = (px - bx)*(px - bx) + (py - by)*(py - by) + (pz - bz)*(pz - bz);

            for (int j = 1; j < k; j++) {
                double cx = centers[j][0], cy = centers[j][1], cz = centers[j][2];
                double d = (px - cx)*(px - cx) + (py - cy)*(py - cy) + (pz - cz)*(pz - cz);
                if (d < bestDist) {
                    bestDist = d;
                    best = j;
                }
            }

            sumx[best] += px;
            sumy[best] += py;
            sumz[best] += pz;
            cnt[best]++;
        }

        // 2) 更新中心（空簇则保持不变）
        vector<array<double,3>> newCenters = centers;
        for (int j = 0; j < k; j++) {
            if (cnt[j] == 0) {
                // 关键注释：空簇不更新，保持原中心
                continue;
            }
            newCenters[j][0] = sumx[j] / cnt[j];
            newCenters[j][1] = sumy[j] / cnt[j];
            newCenters[j][2] = sumz[j] / cnt[j];
        }
        centers.swap(newCenters);
    }
    return centers;
}

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

    int k;
    cin >> k;
    vector<array<double,3>> centers(k);
    for (int i = 0; i < k; i++) {
        cin >> centers[i][0] >> centers[i][1] >> centers[i][2];
    }

    int iters, m;
    cin >> iters >> m;
    vector<array<double,3>> points(m);
    for (int i = 0; i < m; i++) {
        cin >> points[i][0] >> points[i][1] >> points[i][2];
    }

    auto ans = kmeansUpdate(centers, points, iters);

    cout << fixed << setprecision(2);
    for (int i = 0; i < k; i++) {
        cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << "\n";
    }
    return 0;
}

import java.util.*;
public class Main {

    // 题面功能：执行KMeans迭代，返回最终聚类中心
    static double[][] kmeansUpdate(double[][] centers, double[][] points, int iters) {
        int k = centers.length;
        int m = points.length;

        for (int t = 0; t < iters; t++) {
            double[] sumx = new double[k];
            double[] sumy = new double[k];
            double[] sumz = new double[k];
            int[] cnt = new int[k];

            // 1) 分配样本到最近中心
            for (int i = 0; i < m; i++) {
                double px = points[i][0], py = points[i][1], pz = points[i][2];

                int best = 0;
                double bx = centers[0][0], by = centers[0][1], bz = centers[0][2];
                double bestDist = sq(px - bx) + sq(py - by) + sq(pz - bz);

                for (int j = 1; j < k; j++) {
                    double cx = centers[j][0], cy = centers[j][1], cz = centers[j][2];
                    double d = sq(px - cx) + sq(py - cy) + sq(pz - cz);
                    if (d < bestDist) {
                        bestDist = d;
                        best = j;
                    }
                }

                sumx[best] += px;
                sumy[best] += py;
                sumz[best] += pz;
                cnt[best]++;
            }

            // 2) 更新中心（空簇则保持不变）
            double[][] newCenters = new double[k][3];
            for (int j = 0; j < k; j++) {
                if (cnt[j] == 0) {
                    // 关键注释：空簇不更新，保持原中心
                    newCenters[j][0] = centers[j][0];
                    newCenters[j][1] = centers[j][1];
                    newCenters[j][2] = centers[j][2];
                } else {
                    newCenters[j][0] = sumx[j] / cnt[j];
                    newCenters[j][1] = sumy[j] / cnt[j];
                    newCenters[j][2] = sumz[j] / cnt[j];
                }
            }
            centers = newCenters;
        }
        return centers;
    }

    static double sq(double x) {
        return x * x;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int k = sc.nextInt();
        double[][] centers = new double[k][3];
        for (int i = 0; i < k; i++) {
            centers[i][0] = sc.nextDouble();
            centers[i][1] = sc.nextDouble();
            centers[i][2] = sc.nextDouble();
        }

        int iters = sc.nextInt();
        int m = sc.nextInt();
        double[][] points = new double[m][3];
        for (int i = 0; i < m; i++) {
            points[i][0] = sc.nextDouble();
            points[i][1] = sc.nextDouble();
            points[i][2] = sc.nextDouble();
        }

        double[][] ans = kmeansUpdate(centers, points, iters);

        // 输出保留两位小数（四舍五入）
        for (int i = 0; i < k; i++) {
            System.out.printf(Locale.US, "%.2f %.2f %.2f%n", ans[i][0], ans[i][1], ans[i][2]);
        }

        sc.close();
    }
}

题目内容

网络流量分析是网络安全和性能优化的关键任务。假设你有一个包含网络流量数据的数据集，每条数据包含以下特征：

$packet$ _ $size$ (数据包大小，单位，字节)

$inter$ _ $arrival$ _ $time$ (数据包到达间隔时间，单位：毫秒)

$protocol$ _ $type$ (协议类型，如 $TCP、UDP、ICMP$ 等，已转换为数值编码)

你的任务是使用 $KMeans$ 聚类算法对网络流量进行分类，分类后的中心点再经过一个分类头，能识别出可能的流量类型(如正常流量、异常流量、 $DDoS$ 攻击流量等)。 $KMeans$ 算法原理为：先将数据分为 $K$ 组，随机选取 $K$ 个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，将每一个对象分配给距离它最近的聚类中心，聚类中心以及分配给它们的对象就代表一个聚类。(为保证结果固定，本题初始的聚类中心已给出，不需要随机)

输入描述

初始聚类点个数 $k$

初始聚类中心集合(往下 $k$ 行，一行一个中心点)

迭代次数

样本个数 $m$

样本数 $m$ ，每个样本有三个特征(往下 $m$ 行，假定各特征数据已归一化处理，各维度权重占比一致)

输出描述

按给定次数迭代后新的聚类中心集合

样例1

输入

输出

35.33 30.00 30.00
80.00 9.17 60.00
25.67 80.83 90.00

说明

采用欧式距离计算不同数据之间的距离：

$d=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}+\left(z_{1}-z_{2}\right)^{2}}$

计算每个特征距离中心点的距离，选择距离最近的点作为当前特征归属的类别；按照划分的类别，使用重新计算每个类别的中心点，完成一轮迭代(中心点为对应类里所有样本的平均值)

重复上述流程 $k$ 次得到结果，最终结果保留两位小数，注意四舍五入

样例2

输入

3
50 20 30
60 10 60
180 180 180
3
8
50 20 30
30 50 30
60 10 60
25 75 90
100 5 60
30 60 90
80 10 60
180 180 180

输出

40.00 35.00 30.00
59.00 32.00 72.00
180.00 180.00 180.00

说明

采用欧式距离计算不同数据之间的距离：

$d=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}+\left(z_{1}-z_{2}\right)^{2}}$

重复上述流程 $k$ 次得到结果，最终结果保留两位小数，注意四舍五入

提示

取值范围

初始聚类中心点个数： $0<=n<=1000$ ，类型为 $int$

初始聚类中心点集合：每个特征的取值范围为 $0<=f<=1000$ ，类型为 $float$

迭代次数： $0<=k<=1000$ ，类型为 $int$

初始特征个数： $0<=n<=1000$ ，类型为 $int$

初始特征集合：每个特征的取值范围为 $0<=f<=1000$ ，类型为 $float$

#P4571. 第2题-网络流量分析

第2题-网络流量分析

解题思路

复杂度分析

代码实现

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About