企业官网建设流程全解析

目录

题目

思路

Code

题目

题目内容：

K-Median 按划分做聚类：样本之间用曼哈顿距离（L1），簇中心取该簇在每一维上的中位数，因此离群点不容易把中心拉偏。

给定 n 个样本，每个样本有 d 个浮点特征。请按下列固定流程把样本分成 k 个簇，并输出簇编号、最终中心和 inertia。

- 初始化：取下标 0 到 k-1 的样本作为 k 个簇的初始中心。

- 分配：把每个样本分到曼哈顿距离最近的中心。到多个中心的距离相同时，分到编号最小的簇。

- 更新：若某个簇在本轮分配后没有样本，则该簇中心保持不变；否则，用簇内样本在每一维上的中位数替换该簇中心。

重复分配与更新，直到中心变化量小于 tol，或迭代次数达到 max_iter。tol 固定为 10⁻⁴，max_iter 固定为 100。中心变化量是所有簇、所有维度上，新旧中心坐标绝对差的总和。

曼哈顿距离为 dist(x, y) = Σᵢ |xᵢ − yᵢ|。

一维中位数：将数值升序排列后，个数为奇数时取正中间的一项，个数为偶数时取正中间两项的算术平均（可以是浮点数）。例如 [1, 3, 5, 9] 的中位数是 (3+5)/2 = 4。

样例1

输入：

3 2 1 2 8 6 1 4 5

输出：

0 0 0 4.000000 5.000000 11.000000

思路

整体思路：按题面固定流程做 K-Median 迭代模拟——分配（曼哈顿距离最近中心，平局取最小编号）、更新（非空簇逐维取中位数，空簇中心保持）、以全中心绝对变化量之和 < 1e-4 或迭代满 100 轮为停机条件，最后输出簇编号、最终中心与 inertia。

1. 初始化：把前 k 个样本整行拷贝为初始中心，中心与样本分开存储，避免更新中心时污染原始特征。

2. 每轮分配：对每个样本先算到 0 号中心的距离，再依次算其余中心，只有严格更近才切换簇编号，保证并列时落到编号最小的簇。

3. 每轮更新：非空簇对每一维单独排序取中位数（奇数个取正中一项，偶数个取中间两项算术平均）；空簇把旧中心整行原样保留。

4. 停机判断：所有簇、所有维度上新旧中心坐标绝对差之和用双精度累加，小于 1e-4 即停止，最多迭代 100 轮。

5. 输出：最后一轮分配得到的簇编号、停机时的最终中心，以及每个样本到所属中心的曼哈顿距离之和（inertia）。

6. 格式：中心与 inertia 保留 6 位小数；数值为 0 时按正零输出，避免打出 -0.000000。

复杂度：每轮分配 O(n·k·d)，更新 O(n·d·log d)（逐维排序），最多 100 轮，总体 O(100·n·k·d)；空间 O(n·d)。

Code

C++

#include <bits/stdc++.h> using namespace std; static string fmt6(double x) { // 把一个数格式化为固定 6 位小数的字符串，比如 4.1 -> "4.100000" // ostringstream 是 C++ 里"先把内容写进内存字符串"的工具，方便拼接输出 if (x == 0) x = 0.0; // 把"负零"(-0.0)统一成正零，避免打印 "-0.000000" ostringstream oss; oss << fixed << setprecision(6) << x; // fixed+setprecision(6) = 保留 6 位小数 return oss.str(); } int main() { int n, d, k; if (!(cin >> n >> d >> k)) return 0; // 第一行：样本数 n、维数 d、簇数 k // pts[i] 是第 i 个样本的 d 个特征值 vector<vector<double>> pts(n, vector<double>(d)); for (int i = 0; i < n; i++) for (int j = 0; j < d; j++) cin >> pts[i][j]; // ---- 初始化：取前 k 个样本当初始中心 ---- // 这里用迭代器区间拷贝了一份，cen 和 pts 是两份独立数据， // 后面更新中心时不会动到原始样本 vector<vector<double>> cen(pts.begin(), pts.begin() + k); vector<int> lab(n, 0); // lab[i] = 第 i 个样本所属的簇编号 // ---- 迭代：最多 100 轮（题目规定 max_iter = 100）---- for (int iter = 0; iter < 100; iter++) { // ---- 第 1 步：分配：每个样本归到最近的中心 ---- for (int i = 0; i < n; i++) { double bd = 0.0; // best distance：到 0 号中心的曼哈顿距离 for (int j = 0; j < d; j++) bd += fabs(pts[i][j] - cen[0][j]); int best = 0; for (int c = 1; c < k; c++) { double cur = 0.0; // 到 c 号中心的距离：每维差值绝对值求和 for (int j = 0; j < d; j++) cur += fabs(pts[i][j] - cen[c][j]); // 只有"严格更近"才换簇（< 而不是 <=），并列时保留编号更小的簇 if (cur < bd) { bd = cur; best = c; } } lab[i] = best; } // 按簇归组：grp[c] 是 c 号簇里所有样本的下标 vector<vector<int>> grp(k); for (int i = 0; i < n; i++) grp[lab[i]].push_back(i); // ---- 第 2 步：更新：非空簇逐维取中位数 ---- vector<vector<double>> nxt; // 新中心 double shift = 0.0; // 中心变化总量 for (int c = 0; c < k; c++) { if (grp[c].empty()) { // 空簇：没有样本，中心原样保留（题目规定） nxt.push_back(cen[c]); continue; } vector<double> row(d); for (int j = 0; j < d; j++) { // 取出该簇所有样本第 j 维的值 vector<double> vals; for (int idx : grp[c]) vals.push_back(pts[idx][j]); sort(vals.begin(), vals.end()); // 升序排序后取中位数 int m = vals.size(); // 奇数个取正中间一个；偶数个取中间两个的平均 double med = (m % 2 == 1) ? vals[m / 2] : (vals[m / 2 - 1] + vals[m / 2]) / 2.0; row[j] = med; } for (int j = 0; j < d; j++) shift += fabs(row[j] - cen[c][j]); nxt.push_back(row); } cen = nxt; // 用新中心替换旧中心 // ---- 停机判断：变化总量 < 1e-4（即 0.0001）就提前结束 ---- if (shift < 1e-4) break; } // ---- 第 3 步：inertia：每个样本到所属中心的曼哈顿距离之和 ---- double iner = 0.0; for (int i = 0; i < n; i++) for (int j = 0; j < d; j++) iner += fabs(pts[i][j] - cen[lab[i]][j]); // ---- 输出：第一行簇编号，之后 k 行中心，最后一行 inertia ---- for (int i = 0; i < n; i++) cout << (i ? " " : "") << lab[i]; cout << "\n"; for (int c = 0; c < k; c++) { for (int j = 0; j < d; j++) cout << (j ? " " : "") << fmt6(cen[c][j]); cout << "\n"; } cout << fmt6(iner) << "\n"; return 0; }

Java

import java.io.*; import java.util.*; public class Solution { static String fmt6(double x) { // 把一个数格式化为固定 6 位小数的字符串，比如 4.1 -> "4.100000" // Locale.ROOT 保证小数点是 "."，不会被某些系统的语言设置改成逗号 if (x == 0) x = 0.0; // 把"负零"(-0.0)统一成正零，避免输出 "-0.000000" return String.format(Locale.ROOT, "%.6f", x); } static Object[] solve(double[][] pts, int k) { // 整个 K-Median 迭代过程 // 返回 Object[3]：{ int[] 簇编号, double[][] 最终中心, Double inertia 总和 } // （Java 一个方法只能返回一个值，所以把三个结果打包成数组） int n = pts.length; // 样本个数 int d = pts[0].length; // 每个样本的特征维数 // ---- 初始化：取前 k 个样本当初始中心 ---- // clone() 拷贝一份，防止后面更新中心时把原始样本改掉 double[][] cen = new double[k][]; for (int i = 0; i < k; i++) cen[i] = pts[i].clone(); int[] lab = new int[n]; // lab[i] = 第 i 个样本所属的簇编号 // ---- 迭代：最多 100 轮（题目规定 max_iter = 100）---- for (int iter = 0; iter < 100; iter++) { // ---- 第 1 步：分配：每个样本归到最近的中心 ---- for (int i = 0; i < n; i++) { double bd = 0.0; // best distance：到 0 号中心的曼哈顿距离 for (int j = 0; j < d; j++) bd += Math.abs(pts[i][j] - cen[0][j]); int best = 0; for (int c = 1; c < k; c++) { double cur = 0.0; // 到 c 号中心的距离：每维差值绝对值求和 for (int j = 0; j < d; j++) cur += Math.abs(pts[i][j] - cen[c][j]); // 只有"严格更近"才换簇，并列时保留编号更小的簇 if (cur < bd) { bd = cur; best = c; } } lab[i] = best; } // 按簇归组：grp.get(c) 是 c 号簇里所有样本的下标 List<List<Integer>> grp = new ArrayList<>(); for (int c = 0; c < k; c++) grp.add(new ArrayList<>()); for (int i = 0; i < n; i++) grp.get(lab[i]).add(i); // ---- 第 2 步：更新：非空簇逐维取中位数 ---- double[][] nxt = new double[k][]; // 新中心 double shift = 0.0; // 中心变化总量 for (int c = 0; c < k; c++) { if (grp.get(c).isEmpty()) { // 空簇：没有样本，中心原样保留 nxt[c] = cen[c].clone(); continue; } double[] row = new double[d]; for (int j = 0; j < d; j++) { // 收集该簇所有样本第 j 维的值 double[] vals = new double[grp.get(c).size()]; int m = 0; for (int idx : grp.get(c)) vals[m++] = pts[idx][j]; Arrays.sort(vals); // 升序排序 // 奇数个取正中间一个；偶数个取中间两个的平均 row[j] = (vals.length % 2 == 1) ? vals[vals.length / 2] : (vals[vals.length / 2 - 1] + vals[vals.length / 2]) / 2.0; } for (int j = 0; j < d; j++) shift += Math.abs(row[j] - cen[c][j]); nxt[c] = row; } cen = nxt; // 新中心替换旧中心 // ---- 停机判断：变化总量 < 1e-4（即 0.0001）就提前结束 ---- if (shift < 1e-4) break; } // ---- 第 3 步：inertia：每个样本到所属中心的曼哈顿距离之和 ---- double iner = 0.0; for (int i = 0; i < n; i++) for (int j = 0; j < d; j++) iner += Math.abs(pts[i][j] - cen[lab[i]][j]); return new Object[]{lab, cen, iner}; } public static void main(String[] args) { // Scanner 是 Java 最方便的"读输入"工具，nextInt/nextDouble 会自动跳过空白 Scanner sc = new Scanner(new BufferedInputStream(System.in)); int n = sc.nextInt(), d = sc.nextInt(), k = sc.nextInt(); double[][] pts = new double[n][d]; for (int i = 0; i < n; i++) for (int j = 0; j < d; j++) pts[i][j] = sc.nextDouble(); Object[] res = solve(pts, k); int[] lab = (int[]) res[0]; double[][] cen = (double[][]) res[1]; double iner = (Double) res[2]; // 用 StringBuilder 攒输出，最后一次性打印，比多次 System.out 快 StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { if (i > 0) sb.append(' '); sb.append(lab[i]); } sb.append('\n'); for (double[] row : cen) { for (int j = 0; j < d; j++) { if (j > 0) sb.append(' '); sb.append(fmt6(row[j])); } sb.append('\n'); } sb.append(fmt6(iner)).append('\n'); System.out.print(sb); } }

Go

package main import ( "bufio" "fmt" "math" "os" "sort" "strconv" "strings" ) func fmt6(x float64) string { // 把一个数格式化为固定 6 位小数的字符串，比如 4.1 -> "4.100000" // FormatFloat(x, 'f', 6, 64) = 十进制格式、保留 6 位小数、64 位浮点 if x == 0 { x = 0.0 // 把"负零"(-0.0)统一成正零，避免输出 "-0.000000" } return strconv.FormatFloat(x, 'f', 6, 64) } func solve(pts [][]float64, k int) ([]int, [][]float64, float64) { // 整个 K-Median 迭代过程 // 返回值：lab（每个样本的簇编号）、cen（最终中心）、iner（inertia 总和） n := len(pts) // 样本个数 d := len(pts[0]) // 每个样本的特征维数 // ---- 初始化：取前 k 个样本当初始中心 ---- // append([]float64(nil), cen...) 是 Go 里"拷贝一份切片"的常用写法， // 防止后面更新中心时把原始样本改掉 cen := make([][]float64, k) for i := 0; i < k; i++ { cen[i] = append([]float64(nil), pts[i]...) } lab := make([]int, n) // lab[i] = 第 i 个样本所属的簇编号 // ---- 迭代：最多 100 轮（题目规定 max_iter = 100）---- for iter := 0; iter < 100; iter++ { // ---- 第 1 步：分配：每个样本归到最近的中心 ---- for i := 0; i < n; i++ { bd := 0.0 // best distance：到 0 号中心的曼哈顿距离 for j := 0; j < d; j++ { bd += math.Abs(pts[i][j] - cen[0][j]) } best := 0 for c := 1; c < k; c++ { cur := 0.0 // 到 c 号中心的距离：每维差值绝对值求和 for j := 0; j < d; j++ { cur += math.Abs(pts[i][j] - cen[c][j]) } // 只有"严格更近"才换簇，并列时保留编号更小的簇 if cur < bd { bd = cur best = c } } lab[i] = best } // 按簇归组：grp[c] 是 c 号簇里所有样本的下标 grp := make([][]int, k) for i := 0; i < n; i++ { grp[lab[i]] = append(grp[lab[i]], i) } // ---- 第 2 步：更新：非空簇逐维取中位数 ---- nxt := make([][]float64, k) // 新中心 shift := 0.0 // 中心变化总量 for c := 0; c < k; c++ { if len(grp[c]) == 0 { // 空簇：没有样本，中心原样保留（题目规定） nxt[c] = append([]float64(nil), cen[c]...) continue } row := make([]float64, d) for j := 0; j < d; j++ { // 收集该簇所有样本第 j 维的值 vals := make([]float64, 0, len(grp[c])) for _, idx := range grp[c] { vals = append(vals, pts[idx][j]) } sort.Float64s(vals) // 升序排序（Go 自带的浮点排序） // 奇数个取正中间一个；偶数个取中间两个的平均 m := len(vals) if m%2 == 1 { row[j] = vals[m/2] } else { row[j] = (vals[m/2-1] + vals[m/2]) / 2.0 } } for j := 0; j < d; j++ { shift += math.Abs(row[j] - cen[c][j]) } nxt[c] = row } cen = nxt // 新中心替换旧中心 // ---- 停机判断：变化总量 < 1e-4（即 0.0001）就提前结束 ---- if shift < 1e-4 { break } } // ---- 第 3 步：inertia：每个样本到所属中心的曼哈顿距离之和 ---- iner := 0.0 for i := 0; i < n; i++ { for j := 0; j < d; j++ { iner += math.Abs(pts[i][j] - cen[lab[i]][j]) } } return lab, cen, iner } func main() { // 把整个输入读进来按空白切分，不用逐行解析 data, _ := bufio.NewReader(os.Stdin).ReadToEnd() fields := strings.Fields(string(data)) p := 0 // 当前读到第几个字段 // atoi/atof：读一个整数/浮点数并把指针后移（闭包写法，省去到处传 p） atoi := func() int { v, _ := strconv.Atoi(fields[p]); p++; return v } atof := func() float64 { v, _ := strconv.ParseFloat(fields[p], 64); p++; return v } n, d, k := atoi(), atoi(), atoi() // 样本数、维数、簇数 pts := make([][]float64, n) for i := 0; i < n; i++ { pts[i] = make([]float64, d) for j := 0; j < d; j++ { pts[i][j] = atof() } } lab, cen, iner := solve(pts, k) // bufio.Writer 攒着一起写，比每次直接 fmt.Print 快很多 w := bufio.NewWriter(os.Stdout) defer w.Flush() // 函数结束前把缓冲区内容真正输出 for i, v := range lab { if i > 0 { fmt.Fprint(w, " ") } fmt.Fprint(w, v) } fmt.Fprintln(w) for _, row := range cen { for j, v := range row { if j > 0 { fmt.Fprint(w, " ") } fmt.Fprint(w, fmt6(v)) } fmt.Fprintln(w) } fmt.Fprintln(w, fmt6(iner)) }

C

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> /* 把一个数格式化为固定 6 位小数的字符串，比如 4.1 -> "4.100000" C 语言没有方便的小数格式化返回值，所以写进 buf（调用者给的字符数组） */ static void fmt6(char *buf, double x) { if (x == 0) x = 0.0; /* 把"负零"(-0.0)统一成正零，避免打印 "-0.000000" */ sprintf(buf, "%.6f", x); /* %.6f 就是保留 6 位小数 */ } /* qsort 需要的比较函数：返回负数表示 a 排前面，正数表示 b 排前面 */ static int cmpd(const void *a, const void *b) { double x = *(const double *)a, y = *(const double *)b; return (x > y) - (x < y); } int main(void) { int n, d, k; if (scanf("%d %d %d", &n, &d, &k) != 3) return 0; /* 样本数、维数、簇数 */ /* C 语言没有动态数组，用 malloc 申请一块连续内存当二维表用 pts[i*d+j] 就是第 i 个样本的第 j 维（把二维"压平"成一维存） */ double *pts = (double *)malloc(sizeof(double) * n * d); for (int i = 0; i < n * d; i++) scanf("%lf", &pts[i]); /* 中心也用同样方式存：cen[c*d+j] 是 c 号中心的第 j 维 */ double *cen = (double *)malloc(sizeof(double) * k * d); double *nxt = (double *)malloc(sizeof(double) * k * d); /* 初始化：前 k 个样本直接拷贝当初始中心 memcpy = 内存拷贝，相当于把 pts 的前 k*d 个数复制到 cen */ memcpy(cen, pts, sizeof(double) * k * d); int *lab = (int *)malloc(sizeof(int) * n); /* lab[i] = 第 i 个样本的簇编号 */ int *cnt = (int *)malloc(sizeof(int) * k); /* cnt[c] = c 号簇里有多少样本 */ double *vals = (double *)malloc(sizeof(double) * n); /* 取中位数用的临时数组 */ /* ---- 迭代：最多 100 轮（题目规定 max_iter = 100）---- */ for (int iter = 0; iter < 100; iter++) { /* ---- 第 1 步：分配：每个样本归到最近的中心 ---- */ for (int i = 0; i < n; i++) { double bd = 0.0; /* best distance：到 0 号中心的曼哈顿距离 */ for (int j = 0; j < d; j++) bd += fabs(pts[i * d + j] - cen[j]); int best = 0; for (int c = 1; c < k; c++) { double cur = 0.0; /* 到 c 号中心的距离：每维差值绝对值求和 */ for (int j = 0; j < d; j++) cur += fabs(pts[i * d + j] - cen[c * d + j]); /* 只有"严格更近"才换簇，并列时保留编号更小的簇 */ if (cur < bd) { bd = cur; best = c; } } lab[i] = best; } /* 统计每个簇的样本个数，顺便用来判断空簇 */ memset(cnt, 0, sizeof(int) * k); /* memset = 把数组全部清零 */ for (int i = 0; i < n; i++) cnt[lab[i]]++; /* ---- 第 2 步：更新：非空簇逐维取中位数 ---- */ double shift = 0.0; /* 中心变化总量 */ for (int c = 0; c < k; c++) { if (cnt[c] == 0) { /* 空簇：没有样本，中心原样保留（题目规定） */ memcpy(&nxt[c * d], &cen[c * d], sizeof(double) * d); continue; } for (int j = 0; j < d; j++) { /* 收集该簇所有样本第 j 维的值（遍历所有样本，挑出属于 c 簇的） */ int m = 0; for (int i = 0; i < n; i++) if (lab[i] == c) vals[m++] = pts[i * d + j]; qsort(vals, m, sizeof(double), cmpd); /* 升序排序 */ /* 奇数个取正中间一个；偶数个取中间两个的平均 */ double med = (m % 2 == 1) ? vals[m / 2] : (vals[m / 2 - 1] + vals[m / 2]) / 2.0; nxt[c * d + j] = med; } for (int j = 0; j < d; j++) shift += fabs(nxt[c * d + j] - cen[c * d + j]); } memcpy(cen, nxt, sizeof(double) * k * d); /* 新中心替换旧中心 */ /* ---- 停机判断：变化总量 < 1e-4（即 0.0001）就提前结束 ---- */ if (shift < 1e-4) break; } /* ---- 第 3 步：inertia：每个样本到所属中心的曼哈顿距离之和 ---- */ double iner = 0.0; for (int i = 0; i < n; i++) for (int j = 0; j < d; j++) iner += fabs(pts[i * d + j] - cen[lab[i] * d + j]); /* ---- 输出：第一行簇编号，之后 k 行中心，最后一行 inertia ---- */ for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", lab[i]); printf("\n"); char buf[64]; for (int c = 0; c < k; c++) { for (int j = 0; j < d; j++) { fmt6(buf, cen[c * d + j]); printf(j ? " %s" : "%s", buf); } printf("\n"); } fmt6(buf, iner); printf("%s\n", buf); /* malloc 申请的内存要手动释放，好习惯（程序结束也会自动回收） */ free(pts); free(cen); free(nxt); free(lab); free(cnt); free(vals); return 0; }

Python

def fmt6(x): # 把一个数格式化为固定 6 位小数的字符串，比如 4.1 -> "4.100000" # 题目要求"中心"和"inertia"都保留 6 位小数，所以所有浮点数输出前都要经过它 if x == 0: # 小知识：浮点运算可能算出"负零"(-0.0)，直接打印会变成 "-0.000000" # 这里把任何等于 0 的数（包括 -0.0）统一改成正零 0.0 x = 0.0 return format(x, ".6f") def solve(pts, k): # 整个 K-Median 迭代过程都在这里完成 # pts 是所有样本点（二维列表，pts[i] 是第 i 个样本的 d 个特征值） # k 是要聚成的簇数 # 返回三个结果：lab（每个样本的簇编号）、cen（最终中心）、iner（inertia 总和） n = len(pts) # 样本个数 d = len(pts[0]) # 每个样本的特征维数 # ---- 初始化：取前 k 个样本当初始中心 ---- # 注意必须"拷贝一份"，不能直接引用 pts[i] # 否则后面更新中心时会把原始样本数据也改掉，导致距离算错 cen = [pts[i][:] for i in range(k)] # lab[i] 记录第 i 个样本被分到了哪个簇（0 ~ k-1） lab = [0] * n # ---- 迭代：最多 100 轮（题目规定 max_iter = 100）---- for _ in range(100): # ---- 第 1 步：分配（Assignment）---- # 把每个样本分到"曼哈顿距离最近"的中心 for i in range(n): pi = pts[i] # 当前样本 bd = 0.0 # best distance：当前已知的最短距离 for j in range(d): # 曼哈顿距离 = 每一维差值的绝对值再求和 # 比如 (1,2) 到 (4,6) 的距离是 |1-4| + |2-6| = 3 + 4 = 7 bd += abs(pi[j] - cen[0][j]) best = 0 # 目前最近的簇编号，先假设是 0 号簇 for c in range(1, k): cur = 0.0 # 当前样本到 c 号中心的距离 for j in range(d): cur += abs(pi[j] - cen[c][j]) # 关键：只有"严格更近"才换簇（用 < 而不是 <=） # 这样当两个中心距离并列时，样本会留在编号更小的簇，符合题意 if cur < bd: bd = cur best = c lab[i] = best # 按簇编号把样本的下标归组，grp[c] 就是 c 号簇里所有样本的下标列表 grp = [[] for _ in range(k)] for i in range(n): grp[lab[i]].append(i) # ---- 第 2 步：更新（Update）---- nxt = [] # 存放更新后的新中心 shift = 0.0 # 中心变化量：所有簇、所有维度新旧坐标绝对差的总和 for c in range(k): if not grp[c]: # 空簇：这一轮没有任何样本分到它，中心原样保留（题目规定） nxt.append(cen[c][:]) continue row = [] # c 号簇的新中心，一共 d 维 for j in range(d): # 收集该簇所有样本在第 j 维上的取值，排序后取中位数 vals = sorted(pts[i][j] for i in grp[c]) m = len(vals) if m % 2 == 1: # 奇数个：取正中间那一个 med = vals[m // 2] else: # 偶数个：取中间两个的算术平均（题目规定，可以是小数） med = (vals[m // 2 - 1] + vals[m // 2]) / 2.0 row.append(med) for j in range(d): # 累加这一簇每一维的变化量，用于判断要不要继续迭代 shift += abs(row[j] - cen[c][j]) nxt.append(row) cen = nxt # 用新中心替换旧中心，进入下一轮 # ---- 停机判断：变化量之和小于 tol=1e-4 就提前结束 ---- if shift < 1e-4: break # ---- 第 3 步：计算 inertia ---- # inertia = 每个样本到"自己所属簇中心"的曼哈顿距离之和 # 注意用停机那一刻的 lab（最后一次分配结果）和 cen（最后一次更新后的中心） iner = 0.0 for i in range(n): for j in range(d): iner += abs(pts[i][j] - cen[lab[i]][j]) return lab, cen, iner def main(): import sys # 把整个输入读进来按空白切分，比逐行读更省事，也不用担心换行格式 data = sys.stdin.read().split() it = iter(data) # 第一行三个数：样本数 n、维数 d、簇数 k n, d, k = int(next(it)), int(next(it)), int(next(it)) # 接下来 n 行，每行 d 个浮点数，是每个样本的特征值 pts = [[float(next(it)) for _ in range(d)] for _ in range(n)] lab, cen, iner = solve(pts, k) # 输出三部分：第一行所有样本的簇编号；然后 k 行中心；最后一行 inertia lines = [" ".join(map(str, lab))] for row in cen: lines.append(" ".join(fmt6(v) for v in row)) lines.append(fmt6(iner)) sys.stdout.write("\n".join(lines) + "\n") if __name__ == "__main__": main()