首页 > 试题广场 >

小红的 AI 配送聚类优化

[编程题]小红的 AI 配送聚类优化
  • 热度指数：976 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红正在为自研的无人驾驶配送机器人开发一套路径规划系统。为了提高效率，配送系统需要先将分散的包裹坐标通过无监督学习算法进行聚类，确定 K 个核心服务点，然后再由机器人按顺序前往这些点。 小红选用了经典的 K-Means 算法。具体聚类与路径规划逻辑如下： 1. 初始化： - 如果服务中心数量 K 大于或等于包裹总数 N，则每个包裹坐标直接作为最终的服务点坐标。 - 否则，先计算所有包裹到坐标原点 (0,0) 的欧几里得距离，并按距离从小到大排序。若距离相同，保持原始输入顺序。选取排序后的前 K 个包裹坐标作为初始聚类中心，并赋予编号 0 到 K-1。 2. 聚类迭代（最多迭代 50 次）： - 分配阶段：将每个包裹分配给距离其最近的聚类中心。若某包裹到多个中心的距离相等，则分配给编号最小的中心。 - 更新阶段：将每个中心的位置更新为其所分配的所有包裹坐标的平均值。如果某个中心没有分配到任何包裹，则其坐标保持不变。 - 终止条件：计算所有中心在本次更新中移动的欧几里得距离之和。若该距离之和小于 10^{-4}，或者已完成 50 次迭代，则停止。 3. 路径规划与耗时计算： - 聚类完成后，将最终得到的 K 个服务点坐标按其到原点 (0,0) 的欧几里得距离进行升序排列。 - 机器人从原点 (0,0) 出发，依次访问这 K 个点，最后返回原点 (0,0)。 - 计算机器人走完这段闭环路径的总长度，并根据平均时速计算总耗时。 请帮小红计算完成配送任务所需的总秒数。

输入描述:
第一行包含三个空格分隔的整数，分别是服务中心数量 K、包裹总数 N（1 \leq K \leq 10, 1 \leq N \leq 100），以及配送机器人的平均速度 speed（1 \leq speed \leq 100，单位 km/h）。

接下来的 N 行，每行包含两个实数 x_i 和 y_i（-100.0 \leq x_i, y_i \leq 100.0），表示每个包裹在地图上的公里坐标。


输出描述:

	输出一个整数，表示完成任务所需的总时间（秒）。结果请向下取整。
示例1

输入

2 3 36
3.0 4.0
6.0 8.0
0.0 5.0

输出

1710

说明

在本样例中，K=2, N=3，机器速速度为 36 km/h。
1. 包裹到原点的距离分别为 5.0, 10.0, 5.0。排序后选择坐标 (3,4) 为中心 0，(0,5) 为中心 1。
2. 经过聚类迭代，中心 0 最终更新为 (4.5, 6.0)，中心 1 为 (0.0, 5.0)。
3. 两个服务点到原点距离分别为 7.5 和 5.0。访问顺序为 (0,0) -> (0,5) -> (4.5, 6) -> (0,0)。
4. 总路径长度约为 5 + 4.6098 + 7.5 = 17.1098 km。
5. 总耗时约为 17.1098 / 36 \times 3600 = 1710.98 秒，向下取整得 1710。
示例2

输入

3 10 30
1.2 1.5
1.8 1.2
5.0 5.2
5.5 4.8
4.9 5.5
-2.0 3.0
-2.5 3.5
-1.8 2.8
1.5 1.8
5.2 5.0

输出

2502

说明


	For 3 communities, 10 packages, and speed 30 km/h, the 10 packages are clustered into 3 centers. Sorted by distance to the origin, the centers are approximately (1.5, 1.5), (-2.1, 3.1), and (5.15, 5.125). The total distance traversed visiting them in order and returning to the origin takes approximately 2502 seconds (floor applied). Note: if K >= N, all N points become their own cluster centers.
算法知识视频讲解
添加回答
C++
ariadne_头像 ariadne_
C++注意使用stable_sort，不然可能本地正确但是牛客提交错误
发表于 2026-04-14 02:51:49 回复(1)
Python
汀筠拾光头像 汀筠拾光
这道题目是有问题的，示例2和题目要求自相矛盾，示例2英文流程里面2D点的坐标精度都和题目不一样，总之就是我觉得题目有问题。这是我的Python实现：
import sys

def findmin(A):
    i=0
    for j in range(1,len(A)):
        if A[i]>A[j]:
            i=j
    return i

KNs=input("").split()
KNs=[int(KNs[i]) for i in range(3)]
points=[]
for i in range(KNs[1]):
    line=input("").split()
    points.append([float(line[0]),float(line[1])])

points.sort(key=lambda x:x[0]**2+x[1]**2)
centers=points[:]
if KNs[1]>KNs[0]:
    centers=points[:KNs[0]]
    for e in range(50):
        last_cen=[centers[i][:] for i in range(KNs[0])]
        indexs=[[] for i in range(KNs[0])]
        dists=[[pow(pow(centers[i][0]-points[j][0],2)+pow(centers[i][1]-points[j][1],2),0.5) for i in range(KNs[0])] for j in range(KNs[1])]
        for n in range(KNs[1]):
            indexs[findmin(dists[n])].append(n)
        acc=0
        for k in range(KNs[0]):
            if len(indexs[k])<=1:
                continue
            centers[k][0]=sum([points[indexs[k][i]][0] for i in range(len(indexs[k]))])/len(indexs[k])
            centers[k][1]=sum([points[indexs[k][i]][1] for i in range(len(indexs[k]))])/len(indexs[k])
            acc+=pow(pow(centers[k][0]-last_cen[k][0],2)+pow(centers[k][1]-last_cen[k][1],2),0.5)
        if acc<1e-4:
            break

centers.sort(key=lambda x:x[0]**2+x[1]**2)
path=[((centers[0][0])**2+(centers[0][1])**2)**0.5]
for i in range(len(centers)-1):
    path.append(((centers[i+1][0]-centers[i][0])**2+(centers[i+1][1]-centers[i][1])**2)**0.5)
path.append(((centers[-1][0])**2+(centers[-1][1])**2)**0.5)
time=int(sum(path)/KNs[2]*3600)
print(time)


发表于 2026-04-16 15:37:25 回复(1)
提交观点

问题信息

难度：
2条回答 156浏览

热门推荐

相关试题

小红的 AI 配送聚类优化

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号