笔试时间：2025年9月24日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：无线网络优化中的基站聚类分析

【问题背景】在无线网络优化中，基站的位置分布直接影响信号覆盖质量。密集区域的基站可能造成资源浪费，而稀疏区域则会出现信号覆盖不足。

【任务要求】给定n个基站的二维坐标，使用K-Means算法将其划分为k个簇，再通过计算每个簇的轮廓系数（Silhouette Coefficient），识别信号覆盖最差的簇（轮廓系数最低），并在该簇中心新增基站以优化信号覆盖。

算法过程：

1. 使用前k个基站作为初始聚类中心，执行K-Means算法。K-means的结束条件为：最大迭代次数100或者所有簇中心点移动距离都不大于10^-6
2. 计算每个簇的轮廓系数（簇内所有点的轮廓系数平均值）
3. 找出轮廓系数最低的簇
4. 输出该簇的中心坐标（保留两位小数），作为新增基站的位置

输入描述

输出描述

新增基站的坐标：x y（输出结果四舍五入保留两位小数，采用RoundingMode.HALF_EVEN）

样例输入

6 2

0 0

1 1

2 2

10 10

11 11

5 5

样例输出

8.67 8.67

样例说明

簇划分结果：簇0：[(0,0),(1,1),(2,2)]，中心(1,1)；簇1：[(5,5),(10,10),(11,11)]，中心(8.67,8.67)轮廓系数：簇0的轮廓系数：0.82；簇1轮廓系数：0.35答案：输出簇1的中心点：(8.67,8.67)

参考题解

解题思路：

1. 实施K-Means聚类：使用前k个基站作为初始中心，迭代分配点到最近中心并更新中心位置
2. 计算轮廓系数：对每个点计算簇内平均距离a(i)和最近其他簇的平均距离b(i)，s(i)=(b(i)-a(i))/max(a(i),b(i))
3. 找出轮廓系数最低的簇，输出其中心坐标

Python：

import sys
import math
from decimal import Decimal, ROUND_HALF_EVEN

def solve():
    def round_half_even(number, ndigits=2):
        d = Decimal(str(number))
        quantizer = Decimal('1e-' + str(ndigits))
        return d.quantize(quantizer, rounding=ROUND_HALF_EVEN)
    
    def euclidean_distance(p1, p2):
        return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
    
    def squared_euclidean_distance(p1, p2):
        return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
    
    n, k = map(int, sys.stdin.readline().strip().split())
    points = []
    for _ in range(n):
        points.append(list(map(int, sys.stdin.readline().strip().split())))
    
    centers = [list(p) for p in points[:k]]
    max_iterations = 100
    tolerance = 1e-6
    cluster_assignments = [-1] * n
    
    for _ in range(max_iterations):
        clusters = [[] for _ in range(k)]
        for i, point in enumerate(points):
            min_dist_sq = float('inf')
            closest_center_idx = -1
            for j, center in enumerate(centers):
                dist_sq = squared_euclidean_distance(point, center)
                if dist_sq < min_dist_sq:
                    min_dist_sq = dist_sq
                    closest_center_idx = j
            clusters[closest_center_idx].append(i)
            cluster_assignments[i] = closest_center_idx
        
        old_centers = [list(c) for c in centers]
        for j in range(k):
            cluster_point_indices = clusters[j]
            if cluster_point_indices:
                cluster_points = [points[p_idx] for p_idx in cluster_point_indices]
                sum_x = sum(p[0] for p in cluster_points)
                sum_y = sum(p[1] for p in cluster_points)
                num_points = len(cluster_points)
                centers[j] = [sum_x / num_points, sum_y / num_points]
        
        max_shift = 0
        for j in range(k):
            shift = euclidean_distance(centers[j], old_centers[j])
            max_shift = max(max_shift, shift)
        
        if max_shift <= tolerance:
            break
    
    cluster_total_silhouette = [0.0] * k
    cluster_point_counts = [0] * k
    
    for i in range(n):
        point_i = points[i]
        my_cluster_idx = cluster_assignments[i]
        my_cluster_indices = clusters[my_cluster_idx]
        
        if len(my_cluster_indices) <= 1:
            s_i = 1.0
        else:
            sum_dist_a = sum(euclidean_distance(point_i, points[j_idx]) 
                            for j_idx in my_cluster_indices if j_idx != i)
            a_i = sum_dist_a / (len(my_cluster_indices) - 1)
            
            min_avg_dist_b = float('inf')
            for other_cluster_idx in range(k):
                if other_cluster_idx == my_cluster_idx: