🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 70+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🧩 备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至 100 套后，价格会进行一波调整~

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🪔 大疆的秋招第二场笔试，来啦！！！

🍥 大疆有很多套卷，每套卷子有 0/1/2 道编程题，题目内容不一定相同，这样 选择题、填空、问答 的比重就占很大了。

🍉 本道题是一道TSP问题的变种，只不过数据范围很小，直接爆搜即可

💽 LYA的智能农场

问题描述

LYA是一位热爱科技的农场主，她最近购买了一台智能农业机器人来帮助管理她的果园。这个机器人需要从充电站（坐标原点[0,0]）出发，依次访问果园中的每棵果树进行浇水和施肥操作，最后返回充电站。

为了节省能源，LYA希望为机器人规划一条最短的工作路径。已知果园中有 棵果树，每棵果树的位置由其 和 坐标确定。

请你帮助LYA计算出机器人完成所有果树护理工作并返回充电站的最短路径长度。

输入格式

第一行包含两个整数：数据行数（固定为2）和果树数量 。

第二行包含 个整数，表示每棵果树的 坐标。

第三行包含 个整数，表示每棵果树的 坐标。

输出格式

输出一个浮点数，表示机器人完成工作的最短路径长度，精确到小数点后20位。

样例输入

2 3
1 3 5
2 4 6

样例输出

15.70317190289882347543

数据范围

题解

本题是一个变种的旅行商问题（TSP），只不过数据范围非常小。

核心思路是使用 DFS 遍历所有可能的路径，对于所有的路径计算最小的距离，这个过程可以看成是求全排列。

需要注意的是起点和终点都是充电站，且路径长度计算要考虑欧几里得距离。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

import math

def calculate_distance(a, b):
    """计算两点之间的欧几里得距离"""
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def dfs(u, cost, last, mask, trees, n):
    """深度优先搜索遍历所有可能路径"""
    global min_distance
    if u == n:
        min_distance = min(min_distance, cost)
        return
    for i in range(n):
        if mask & (1 << i):
            new_mask = mask ^ (1 << i)
            new_cost = cost
            if u > 0:
                new_cost += calculate_distance(trees[i], trees[last])
            if u == 0 or u == n - 1:
                new_cost += calculate_distance(trees[i], [0, 0])
            dfs(u + 1, new_cost, i, new_mask, trees, n)

# 读取输入
_, n = map(int, input().split())
x_coords = list(map(int, input().split()))
y_coords = list(map(int, input().split()))

# 构建树的坐标列表
trees = list(zip(x_coords, y_coords))

# 初始化全局最小距离
min_distance = float('inf')

# 调用DFS函数
dfs(0, 0, -1, (1 << n) - 1, trees, n)

# 输出结果
print(f"{min_distance:.20f}")

• Java

import java.util.*;

public class Main {
    static double minDistance = Double.MAX_VALUE;
    
    publi