【春招笔试】2025.03.12-小米春招笔试

题目总结

题目一：登山计划优化

1️⃣：计算相邻特定日期之间的间隔成本

2️⃣：对间隔成本排序，优先合并成本低的区间

3️⃣：贪心选择尽可能多的区间合并，计算最终移动次数

难度：中等

这道题目考察贪心算法的应用。关键在于理解问题可以转化为区间合并问题，并且应该优先合并间隔小的相邻特定日期，以最大化合并区间的数量。通过排序和贪心选择，可以在 O(n log n) 的时间复杂度内解决问题。

题目二：汽车采购方案优化

1️⃣：将每种汽车的每种配置方案视为独立物品

2️⃣：构建二维完全背包DP模型

3️⃣：状态转移求解最小采购成本

难度：中等偏难

这道题目是二维完全背包问题的变种，需要同时满足载人和载货两个约束条件，目标是最小化总成本。关键在于正确构建状态转移方程，并处理好边界条件。时间复杂度为 O(X×Y×(n+∑k_i))，其中 X 和 Y 分别是载人和载货需求，n 是汽车型号数量，∑k_i