P5411. CDN 节点聚类选址与用户覆盖计算

场次：2026年9月9日 · 来源：CodeFun2000 P5411

题目描述

在内容运营平台中，CDN 分发服务器用于为用户提供就近的内容下载服务。现有 $p$ 座城市，每座城市具有二维坐标和用户数。平台计划建设 $q$ 台 CDN，以兼顾覆盖用户规模与空间距离，使全体用户的加权总距离尽可能小。请按照 k-means 聚类流程确定每台 CDN 的选址坐标及其覆盖用户数。

计算过程遵循以下规则：

初始时，地图上尚未部署任何 CDN；
CDN 必须位于某一座城市的坐标上；
迭代开始时，将输入顺序中的前 $q$ 座城市作为初始 CDN 选址；
每一轮迭代中，先为每座城市分配距离最近的一台 CDN；若某座城市到多台 CDN 的距离相等，则将其分配给编号更靠前的那一台；
针对每台 CDN 当前覆盖的城市集合，重新选择一座集合内的城市作为新的 CDN 选址，使该集合内所有用户到该城市的加权距离总和最小；若有多座城市并列最优，则选择原输入中编号更靠前的一座；
当所有 CDN 所在城市不再变化时，停止迭代。

城市坐标为 $(x, y)$ ，CDN 坐标为 $(c_x, c_y)$ 。一名用户到某台 CDN 的距离定义为欧氏距离：

$d = \sqrt{(x - c_x)^2 + (y - c_y)^2}$

若第 $i$ 座城市的用户数为 $u_i$ ，其被分配到的 CDN 编号为 $z_i$ ，则该 CDN 坐标为 $(c_{x,z_i}, c_{y,z_i})$ 。全体用户的加权总距离为：

$Total = \sum_{i=1}^{p} u_i \cdot \sqrt{(x_i - c_{x,z_i})^2 + (y_i - c_{y,z_i})^2}$

每台 CDN 的覆盖用户数等于被分配至该 CDN 的所有城市的用户数之和。

约束条件：

城市数量 $p$ 为正整数，满足 $0 < p < 100$ ；
每座城市的横坐标、纵坐标和用户数均为浮点数，数值均大于 0 且小于 100；
CDN 数量 $q$ 为正整数，满足 $0 < q < 100$ 且 $q \le p$ 。

输入格式

第一行包含一个正整数 $p$ ，表示城市数量。

接下来 $p$ 行，每行包含三个以英文逗号分隔的浮点数 $a,b,c$ ，依次表示该城市的横坐标、纵坐标和用户数，单位为万人。

最后一行包含一个正整数 $q$ ，表示允许建设的 CDN 数量。

输出格式

输出 $q$ 行，每行包含三个以英文逗号分隔的浮点数 $a,b,c$ ，依次表示一台 CDN 的横坐标、纵坐标及其覆盖用户数，单位为万人。所有浮点数均保留 2 位小数。

CDN 按横坐标 $a$ 升序输出；若横坐标相同，则按纵坐标 $b$ 升序输出。

示例

示例 1

输入：

4
1.00,1.00,10.00
2.00,1.00,1.00
5.00,5.00,1.00
6.00,5.00,10.00
2

输出：

1.00,1.00,11.00
6.00,5.00,11.00

说明：

按输入顺序将城市记为 0、1、2、3。初始时，前 2 座城市分别作为第 1 台和第 2 台 CDN 的选址，即 $(1.00,1.00)$ 与 $(2.00,1.00)$ 。

第一轮分配中，城市 0 到 $(1.00,1.00)$ 的距离为 $0$ ，分配给第 1 台 CDN；城市 1 到 $(2.00,1.00)$ 的距离为 $0$ ，分配给第 2 台 CDN。城市 2 到 $(1.00,1.00)$ 的距离约为 $5.66$ ，到 $(2.00,1.00)$ 的距离为 $5.00$ ，分配给第 2 台 CDN。城市 3 到 $(1.00,1.00)$ 的距离约为 $6.40$ ，到 $(2.00,1.00)$ 的距离约为 $5.66$ ，也分配给第 2 台 CDN。

因此第 1 台 CDN 的簇只包含城市 0；第 2 台 CDN 的簇包含城市 1、2、3。第一轮重新选址时，第 1 台簇内只有城市 0，仍选城市 0。第 2 台簇内以城市 1、2、3 分别作为候选，加权距离和约为 $61.57$ 、 $15.00$ 、 $6.66$ ，因此选择城市 3，坐标为 $(6.00,5.00)$ 。

第二轮分配中，城市 0 和城市 1 距离 $(1.00,1.00)$ 更近，分配给第 1 台 CDN；城市 2 和城市 3 距离 $(6.00,5.00)$ 更近，分配给第 2 台 CDN。第二轮重新选址时，第 1 台簇中城市 0 的加权距离和为 $1.00$ ，城市 1 为 $10.00$ ，仍选城市 0；第 2 台簇中城市 2 的加权距离和为 $10.00$ ，城市 3 为 $1.00$ ，仍选城市 3。选址不再变化，停止迭代。

最终第 1 台 CDN 位于 $(1.00,1.00)$ ，覆盖城市 0 和城市 1，用户数为 $10.00+1.00=11.00$ ；第 2 台 CDN 位于 $(6.00,5.00)$ ，覆盖城市 2 和城市 3，用户数为 $1.00+10.00=11.00$ 。按横坐标升序输出。

示例 2

输入：

1
5.50,6.25,7.75
1

输出：

5.50,6.25,7.75

说明：

只有 1 座城市和 1 台 CDN。初始 CDN 选址就是该城市 $(5.50,6.25)$ 。

该城市到 CDN 的距离为 $0$ ，加权距离和为 $7.75 \times 0 = 0$ ，因此选址不会发生变化。最终 CDN 坐标仍为 $(5.50,6.25)$ ，覆盖用户数为该城市的用户数 7.75 万人。

示例 3

输入：

3
1.00,1.00,2.00
1.00,3.00,4.00
4.00,2.00,6.00
3

输出：

00,1.00,2.00
00,3.00,4.00
00,2.00,6.00

说明：

CDN 数量与城市数量相同，共有 3 座城市和 3 台 CDN。初始时前 3 座城市各自作为一台 CDN 的选址。

每座城市到自身 CDN 的距离都是 $0$ ，到其他 CDN 的距离均大于 $0$ ，因此分配结果固定为每座城市归属自己的 CDN。每个簇只有一座城市，重新选择时选址保持不变。

最终按横坐标、纵坐标升序输出： $(1.00,1.00)$ 覆盖用户数 2.00， $(1.00,3.00)$ 覆盖用户数 4.00， $(4.00,2.00)$ 覆盖用户数 6.00。

解题思路

第一步：理解问题本质

这是把 k-means 聚类落到“CDN 选址”场景里的模拟题：算法流程题目已经规定好，我们要做的是一步不差地照做。流程只有两步，反复交替：

分配：每座城市找距离最近的 CDN；
更新：每台 CDN 在自己的簇里重新选一个位置，使簇内所有用户到它的加权距离和最小。

和标准 k-means 相比，本题有三处“非标准”的设定，必须逐条照办：

CDN 只能落在某座城市的坐标上。所以“更新”不是求均值点，而是在簇内的城市里挑一个最优的（这类做法通常叫 k-medoids）。
初始选址固定：按输入顺序的前 $q$ 座城市，不是随机选、也不是最远点采样。这让答案唯一。
两处平局规则：分配时距离相同 → 分给编号更小的 CDN；更新时加权距离和相同 → 选输入编号更小的城市。

输出时还要注意：不是按 CDN 编号输出，而是按坐标 $(a,b)$ 升序；每行是“横坐标,纵坐标,覆盖用户数”，都保留两位小数。

第二步：暴力解法——直接照规则模拟

最直白的写法就是逐字翻译题目：用浮点坐标存 CDN 位置，每轮重新给所有城市算距离、重新给每台 CDN 枚举候选城市。

centers = [cities[i][:2] for i in range(q)]   # 前 q 座城市

while True:
    groups = [[] for _ in range(q)]
    for i, (x, y, u) in enumerate(cities):
        best, bestd = 0, None
        for k in range(q):
            d = math.dist((x, y), centers[k])
            if bestd is None or d < bestd:
                bestd, best = d, k
        groups[best].append(i)

    new_centers = centers[:]
    for k in range(q):
        bestv, bestc = None, None
        for cand in groups[k]:
            xc, yc, _ = cities[cand]
            v = sum(cities[j][2] * math.dist((cities[j][0], cities[j][1]), (xc, yc))
                    for j in groups[k])
            if bestv is None or v < bestv:
                bestv, bestc = v, cand
        new_centers[k] = cities[bestc][:2]

    if new_centers == centers:
        break
    centers = new_centers

复杂度已经是 $O(K\cdot(pq+p^2))$ ， $p<100$ 时非常宽松 —— 本题的复杂度没有进一步压缩的余地，因为题目规定必须按这套流程迭代。真正需要打磨的是这份代码的三个隐患：

用浮点坐标判断“位置没变”：本题的坐标是从城市表里直接拷过来的，看似没问题；但题目真正要问的是“CDN 是否还在同一座城市”，而不是“两个浮点数是否逐位相等”。只要某处改成重新计算坐标（例如取均值、或先乘除再还原），== 就会因为 $10^{-16}$ 级别的误差判不出相等，直接死循环。
用浮点距离判断平局：题目明确有平局规则，而 d1 < d2 在数学上相等的两个距离上可能因为舍入误差被判成不等，平局规则于是形同虚设，答案会随计算顺序改变。
簇为空时没有定义：如果两台 CDN 落在同一座城市，或某台 CDN 的城市被更靠前的 CDN 抢走，它的簇可能是空的，此时“在簇内选城市”根本无解。

第三步：优化解法——用“城市编号”表示选址

针对上面三个隐患，把 CDN 的位置从“坐标”改成“城市编号”：

第 $k$ 台 CDN 记作 center[k] = 某座城市的编号，坐标随时从城市表里查；
判断“选址是否变化”变成比较两个整数列表，精确且不会死循环；
分配时比较平方距离即可： $d_1<d_2\iff d_1^2<d_2^2$ ，省掉 $p\times q$ 次开方；
平局处理写进比较条件里：只有“严格更近”才换 CDN、只有“严格更小”才换候选城市。

于是每轮迭代的两个子步骤变成：

# 分配：k 从小到大扫，只有严格更近才更新 => 平局自动留给编号小的 CDN
for i in range(p):
    best, best_d2 = 0, float("inf")
    for k in range(q):
        d2 = distance_sq(i, center[k])
        if d2 < best_d2 - 1e-9:
            best_d2, best = d2, k

# 更新：候选按编号升序扫，只有严格更小才更新 => 平局自动留给编号小的城市
for cand in members:
    cost = sum(users[j] * math.hypot(xs[j] - xc, ys[j] - yc) for j in members)
    if best_cost is None or cost < best_cost - 1e-6:
        best_cost, best_city = cost, cand

两处比较都留了一点容差。原因是：对称布局下两个本应相等的量，用浮点算出来可能差 $10^{-13}$ 量级。容差远小于任何“真实的”差距，却能把这种伪差异抹平，让平局规则真正生效。

第四步：最优解法——把细节补全

最后把容易漏的细节固定下来，得到可以放心提交的版本：

距离的两套用法：
- 分配时只比较大小，用平方距离（等价且省开方）；
- 更新时要算加权和，必须用真实欧氏距离 hypot。因为 $\sqrt{a^2+b^2}$ 不是线性的，拿平方距离去加权会把远处的城市放大，选出错误的城市。
空簇处理：簇为空就没有候选城市，让这台 CDN 保持原位。这是题目规则在空集上的自然延伸，也保证迭代不会因为无解而中断。
收敛判定：所有 CDN 的城市编号都不再变化就停止。用 for 循环加一个很大的上限（代码里是 $1000$ 轮）兜底，防止极端平局下的循环；正常情况下十几轮就收敛。
最终再分配一次：迭代停止后再用最终坐标分配一遍，保证输出的“覆盖用户数”和输出的坐标是同一套划分。
输出：按 $(x,y)$ 排序，f"{v:.2f}" 保留两位小数，用逗号连接；还要处理 -0.00（本题所有数值都为正，加一层保护即可）。

完整代码实现

"""
P5411. CDN 节点聚类选址与用户覆盖计算 - 按规则模拟 k-means
"""

import math
import sys


def format_number(value: float) -> str:
    """保留两位小数，并避免输出 -0.00。"""
    if abs(value) < 0.005:
        value = 0.0
    return f"{value:.2f}"


def solve():
    """读入城市与 CDN 数量，模拟 k-means 迭代后输出选址与覆盖用户数。"""
    # 输入是“逗号分隔的浮点数”，把逗号统一换成空格再切分，解析最简单
    tokens = sys.stdin.read().replace(",", " ").split()
    if not tokens:
        return

    p = int(tokens[0])
    pos = 1
    xs = [0.0] * p
    ys = [0.0] * p
    users = [0.0] * p
    for i in range(p):
        xs[i] = float(tokens[pos])
        ys[i] = float(tokens[pos + 1])
        users[i] = float(tokens[pos + 2])
        pos += 3
    q = int(tokens[pos])

    q = min(q, p)  # 题目保证 q <= p，这里兜一层避免越界

    # center[k] 是第 k 台 CDN 当前所在的城市编号。
    # 用编号而不是坐标，判“选址是否变化”时直接比较整数即可。
    center = list(range(q))

    def distance_sq(i: int, city: int) -> float:
        dx = xs[i] - xs[city]
        dy = ys[i] - ys[city]
        return dx * dx + dy * dy

    def assign_cities():
        """把每座城市分配给最近的 CDN，返回分配结果与每个簇的成员列表。"""
        assign = [0] * p
        clusters = [[] for _ in range(q)]
        for i in range(p):
            best = 0
            best_d2 = float("inf")
            for k in range(q):
                d2 = distance_sq(i, center[k])
                # 严格更近才换人 => 距离相等时保留编号更小的 CDN
                if d2 < best_d2 - 1e-9:
                    best_d2 = d2
                    best = k
            assign[i] = best
            clusters[best].append(i)
        return assign, clusters

    def update_centers(clusters):
        """在每台 CDN 的簇内重新选址，返回新的城市编号列表。"""
        new_center = center[:]
        for k in range(q):
            members = clusters[k]
            if not members:
                # 簇为空（例如两台 CDN 落在同一点），没有候选城市，保持原位
                continue
            best_city = members[0]
            best_cost = None
            for cand in members:
                cost = 0.0
                xc = xs[cand]
                yc = ys[cand]
                for j in members:
                    # 加权和必须用真实欧氏距离，不能用平方距离代替
                    dist = math.hypot(xs[j] - xc, ys[j] - yc)
                    cost += users[j] * dist
                # members 按输入编号升序，只有“明显更小”才换 => 平局留编号小的
                if best_cost is None or cost < best_cost - 1e-6:
                    best_cost = cost
                    best_city = cand
            new_center[k] = best_city
        return new_center

    # 迭代到选址不再变化为止。理论上一定收敛，这里给一个上限兜底。
    for _ in range(1000):
        assign, clusters = assign_cities()
        new_center = update_centers(clusters)
        if new_center == center:
            break
        center = new_center

    # 用最终选址再分配一次，保证“覆盖用户数”与输出的坐标是同一套分配
    assign, clusters = assign_cities()

    coverage = [0.0] * q
    for i in range(p):
        coverage[assign[i]] += users[i]

    # 按横坐标升序、横坐标相同按纵坐标升序输出
    rows = [(xs[center[k]], ys[center[k]], coverage[k]) for k in range(q)]
    rows.sort(key=lambda row: (row[0], row[1]))

    lines = [",".join(format_number(v) for v in row) for row in rows]
    sys.stdout.write("\n".join(lines) + ("\n" if lines else ""))


if __name__ == "__main__":
    solve()

NumPy 版本

以下版本使用 NumPy。只有在评测环境允许第三方库时才能提交；CodeFun2000 的普通 Python 环境不一定安装 NumPy。

思路与纯 Python 版完全一致，只是把两处双层循环换成了矩阵运算：全城市两两距离一次算出（分配时取一列比较平方距离），更新步则算一次 D @ W —— 其中 W[j, k] 只在「城市 j 属于簇 k」时等于该城市的用户数，乘出来的一列就是一台 CDN 所有候选城市的加权距离和。

"""
P5411. CDN 节点聚类选址与用户覆盖计算 - NumPy 版

把“给每座城市算到 q 台 CDN 的距离”和“簇内枚举候选城市”都写成矩阵运算：
- 全城市两两距离矩阵一次算出，分配时只取列比较；
- 更新时算「距离矩阵 @ 覆盖权重矩阵」，一列就是一台 CDN 所有候选的加权距离和。

时间复杂度：O(K·p^2)（K 为迭代轮数）；空间复杂度：O(p^2)。
"""

import sys

import numpy as np


def format_number(value: float) -> str:
    """保留两位小数，并避免输出 -0.00。"""
    if abs(value) < 0.005:
        value = 0.0
    return f"{value:.2f}"


def solve():
    # 输入是“逗号分隔的浮点数”，把逗号统一换成空格再切分
    tokens = sys.stdin.read().replace(",", " ").split()
    if not tokens:
        return

    p = int(tokens[0])
    table = np.array(list(map(float, tokens[1:1 + 3 * p])), dtype=np.float64).reshape(p, 3)
    xs = table[:, 0]
    ys = table[:, 1]
    users = table[:, 2]

    q = int(tokens[1 + 3 * p])
    q = min(q, p)                       # 题目保证 q <= p，这里兜一层避免越界

    # 全城市两两距离矩阵：D[i, j] 是城市 i 到城市 j 的距离。
    # 分配时只需要比较平方距离，所以另存一份 D2（不开方，省 p*q 次开方）。
    dx = xs[:, None] - xs[None, :]
    dy = ys[:, None] - ys[None, :]
    D2 = dx * dx + dy * dy
    D = np.hypot(dx, dy)

    # center[k] 是第 k 台 CDN 当前所在的城市编号（用编号判收敛，精确且不会死循环）
    center = np.arange(q)

    def assign_cities():
        """把每座城市分配给最近的 CDN：k 升序扫，只有严格更近才换人。"""
        assign = np.zeros(p, dtype=np.int64)
        best_d2 = np.full(p, np.inf)
        for k in range(q):
            d2 = D2[:, center[k]]
            better = d2 < best_d2 - 1e-9        # 留容差：平局时保留编号更小的 CDN
            assign[better] = k
            best_d2[better] = d2[better]
        return assign

    def update_centers(assign):
        """在每台 CDN 的簇内重新选址：加权距离和最小者胜，平局留编号小的城市。"""
        # W[j, k] = 城市 j 的用户数（j 属于簇 k 时）否则 0，
        # 于是 (D @ W)[i, k] 就是“把簇 k 的 CDN 挪到城市 i”的加权距离和。
        W = np.zeros((p, q), dtype=np.float64)
        W[np.arange(p), assign] = users
        cost = D @ W

        valid = np.zeros((p, q), dtype=bool)
        valid[np.arange(p), assign] = True

        new_center = center.copy()              # 空簇没有候选城市，保持原位
        best_cost = np.full(q, np.inf)
        for cand in range(p):                   # 候选按编号升序扫 => 平局留编号小的
            better = valid[cand] & (cost[cand] < best_cost - 1e-6)
            if better.any():
                best_cost[better] = cost[cand][better]
                new_center[better] = cand
        return new_center

    # 迭代到选址不再变化为止（选址用城市编号表示，比较是精确的）
    for _ in range(1000):
        assign = assign_cities()
        new_center = update_centers(assign)
        if np.array_equal(new_center, center):
            break
        center = new_center

    # 用最终选址再分配一次，保证“覆盖用户数”与输出的坐标是同一套划分
    assign = assign_cities()
    coverage = np.bincount(assign, weights=users, minlength=q)

    # 按横坐标升序、横坐标相同按纵坐标升序输出
    cx = xs[center]
    cy = ys[center]
    order = np.lexsort((cy, cx))
    lines = [
        ",".join(format_number(float(v)) for v in (cx[k], cy[k], coverage[k]))
        for k in order
    ]
    sys.stdout.write("\n".join(lines) + ("\n" if lines else ""))


if __name__ == "__main__":
    solve()

示例推演

样例 1

$p=4$ 、 $q=2$ 。初始时第 1 台 CDN 在城 0 $(1,1)$ ，第 2 台在城 1 $(2,1)$ 。

第一轮分配：

城市	坐标	用户数	到 $(1,1)$	到 $(2,1)$	分配给
0	$(1,1)$	10	$0$	$1.00$	CDN 1
1	$(2,1)$	1	$1.00$	$0$	CDN 2
2	$(5,5)$	1	$\sqrt{32}\approx5.657$	$\sqrt{25}=5.00$	CDN 2
3	$(6,5)$	10	$\sqrt{41}\approx6.403$	$\sqrt{32}\approx5.657$	CDN 2

两个簇分别是 $\{0\}$ 与 $\{1,2,3\}$ 。

第一轮更新：

CDN 1 的簇只有城 0，只能选城 0，位置不变。
CDN 2 在 $\{1,2,3\}$ 里挑一个候选，算加权距离和：

候选	计算	加权距离和
城 1 $(2,1)$	$1\times0+1\times5+10\times5.657$	$61.57$
城 2 $(5,5)$	$1\times5+1\times0+10\times1$	$15.00$
城 3 $(6,5)$	$1\times5.657+1\times1+10\times0$	$6.66$

最小的是城 3，所以 CDN 2 搬到 $(6,5)$ 。此时选址为 $[0,3]$ ，发生了变化，继续。

第二轮分配：

城市	到 $(1,1)$	到 $(6,5)$	分配给
0	$0$	$6.403$	CDN 1
1	$1.00$	$5.657$	CDN 1
2	$5.657$	$1.00$	CDN 2
3	$6.403$	$0$	CDN 2

簇变成 $\{0,1\}$ 与 $\{2,3\}$ 。

第二轮更新：

CDN 1：候选城 0 的加权和是 $10\times0+1\times1=1.00$ ，候选城 1 是 $10\times1+1\times0=10.00$ ，选城 0。
CDN 2：候选城 2 的加权和是 $1\times0+10\times1=10.00$ ，候选城 3 是 $1\times1+10\times0=1.00$ ，选城 3。

选址仍是 $[0,3]$ ，与上一轮相同，停止迭代。

覆盖用户数：CDN 1 覆盖城 0、1，共 $10+1=11$ ；CDN 2 覆盖城 2、3，共 $1+10=11$ 。按横坐标排序输出：

1.00,1.00,11.00
6.00,5.00,11.00

样例 2

$p=1$ 、 $q=1$ ，唯一一座城市 $(5.50,6.25)$ ，用户数 $7.75$ 。初始 CDN 就在这座城上，城市到自己的距离为 $0$ ，簇内只有它自己，更新后位置不变，一轮就收敛。直接输出 5.50,6.25,7.75。

样例 3

$p=q=3$ ，每台 CDN 的初始位置各不相同。每座城市到自己的 CDN 距离为 $0$ ，到其他 CDN 都大于 $0$ ，所以分配结果固定为“一城一簇”。每个簇只有一座城市，更新时没有别的候选，位置不变，一轮收敛。覆盖用户数就是各城自己的用户数 $2$ 、 $4$ 、 $6$ ，按坐标排序输出：

00,1.00,2.00
00,3.00,4.00
00,2.00,6.00

复杂度分析

解法	时间复杂度	空间复杂度	说明
直接按坐标模拟	$O(K\cdot(pq+p^2))$	$O(p+q)$	每轮都用浮点坐标算距离，平局与收敛判定都不稳
按城市编号模拟（本题）	$O(K\cdot(pq+p^2))$	$O(p+q)$	收敛判定变成整数比较，分配时用平方距离
单轮迭代	$O(pq+p^2)$	$O(p+q)$	分配 $p\times q$ ，更新时每簇最多 $

其中 $K$ 是迭代轮数。 $p<100$ ，所以 $pq+p^2<2\times10^4$ ，即使 $K$ 取到几百也毫无压力；实际数据通常十几轮就收敛。

易错点总结

1. 初始选址是“输入顺序的前 $q$ 座城市”

不是随机采样，也不是“选相距最远的 $q$ 座”。题目写死了初始值，这一步错了后面全错。

2. 分配时的平局给编号更小的 CDN

实现上不要写 if d2 < best_d2 之后再单独判等，直接把比较写成“严格更小才更新”，并且 $k$ 从 $0$ 开始升序扫，平局自然保留编号小的那台。

3. 更新时的平局给输入编号更小的城市

同理，候选城市按输入编号升序扫，只有“严格更小”才替换。若用 min(..., key=...)，注意 Python 的 min 在并列时返回第一个，行为一致，但要保证候选列表是按编号升序的。

4. 分配用平方距离，更新必须用真实距离

$d_1<d_2\iff d_1^2<d_2^2$ ，所以分配阶段省掉开方没问题；但更新阶段算的是 $\sum u_j\cdot d(cand,j)$ ， $\sqrt{\cdot}$ 不是线性的，用平方距离加权会系统性地偏向远处的城市，选出错误候选。

5. 空簇要保持原位

当两台 CDN 落在同一坐标，或某台 CDN 的城市被更靠前的 CDN 抢走时，簇可能为空。题目没有单独说明空簇，但“在簇内选一座城市”对空集无解，唯一合理的处理是保持原位。否则会越界或直接崩溃。

6. 收敛判断比较“城市编号”，不要比较坐标

比较整数列表既精确又直观。如果比较浮点坐标，一旦某轮选址只是数值上差了 $10^{-16}$ ，就会永远判不出收敛。

7. 覆盖用户数要基于最终那一轮分配

迭代结束后要再分配一次，用最终坐标统计覆盖人数。直接沿用最后一轮更新前的分配结果，在“最后一轮位置发生了变化但循环因上限退出”的极端情况下会与输出的坐标不一致。

8. 输出格式

按 $(x,y)$ 升序（不是 CDN 编号顺序），每行 a,b,c 用英文逗号连接、没有空格，三个数都保留两位小数。排序键要写成 (x, y) 的元组，只按 $x$ 排会在横坐标相同时顺序错误。

扩展思考

k-medoids 与 k-means 的区别：标准 k-means 的更新步取簇内均值点，是“平方距离和”的最优解，但均值点可能不在任何城市上；本题要求中心必须是真实城市，更新步只能枚举候选，这正是 k-medoids（PAM）的思路。
初始化的影响：k-means 类算法对初始中心敏感，不同初始值可能收敛到不同的局部最优。题目固定“前 $q$ 座城市”作为初始值，正是为了让答案唯一、可判题。
迭代次数：每轮目标函数（全体用户加权总距离）不增且有下界，配合固定的平局规则，实际收敛很快；代码里 $1000$ 轮的上限只是兜底。
规模变大时：若 $p$ 到 $10^5$ ，每轮 $p\times q$ 的暴力分配不可行，需要用 KD 树、球树或 Elkan 算法剪枝；更新步也可以在簇内用增量方式维护加权距离和。
一个有趣的边界： $q=p$ 时每座城市自成一簇，第一轮就收敛，输出就是“按坐标排序后的城市表 + 各自用户数”。

题目描述​

输入格式​

输出格式​

示例​

示例 1​

示例 2​

示例 3​

解题思路​

第一步：理解问题本质​

第二步：暴力解法——直接照规则模拟​

第三步：优化解法——用“城市编号”表示选址​

第四步：最优解法——把细节补全​

完整代码实现​

NumPy 版本​

示例推演​

样例 1​

样例 2​

样例 3​

复杂度分析​

易错点总结​

1. 初始选址是“输入顺序的前 qqq 座城市”​

2. 分配时的平局给编号更小的 CDN​

3. 更新时的平局给输入编号更小的城市​

4. 分配用平方距离，更新必须用真实距离​

5. 空簇要保持原位​

6. 收敛判断比较“城市编号”，不要比较坐标​

7. 覆盖用户数要基于最终那一轮分配​

8. 输出格式​

扩展思考​

相关题目​

题目描述

输入格式

输出格式

示例

示例 1

示例 2

示例 3

解题思路

第一步：理解问题本质

第二步：暴力解法——直接照规则模拟

第三步：优化解法——用“城市编号”表示选址

第四步：最优解法——把细节补全

完整代码实现

NumPy 版本

示例推演

样例 1

样例 2

样例 3

复杂度分析

易错点总结

1. 初始选址是“输入顺序的前 $q$ 座城市”

2. 分配时的平局给编号更小的 CDN

3. 更新时的平局给输入编号更小的城市

4. 分配用平方距离，更新必须用真实距离

5. 空簇要保持原位

6. 收敛判断比较“城市编号”，不要比较坐标

7. 覆盖用户数要基于最终那一轮分配

8. 输出格式

扩展思考

相关题目