0809网易秋招笔试分享

#秋招笔面试记录#
#牛客AI配图神器#

------------------------------------

题目一：

题目大意：
有 n (1 <= n <= 10000) 名学生报名三个社团 A、B、C，每个社团有固定的人数上限。系统按学生提交报名表的时间顺序处理，并根据学生的志愿优先级（1-3个志愿）进行分配。如果第一志愿已满，则尝试第二志愿，以此类推。你需要统计最终每个社团的成员名单。

解法思路：
这是一道直接的模拟题，核心是遵循“先到先得”和“志愿优先”的规则。维护三个社团的剩余名额。按顺序读入每个学生的信息，然后遍历该学生的志愿列表。对于每个志愿，检查对应社团是否还有名额。如果有，则将该学生分配到该社团，减少一个名额，并立即停止处理该学生的后续志愿，转而处理下一个学生。如果所有志愿都尝试过但都已满员，则该学生无法加入任何社团。

------------------------------------

题目二：

题目大意：
有 n (1 <= n <= 3000) 个音乐团体，每个团体有 m (1 <= m <= 100) 名成员，每位成员都有一个演出水平评分。你需要从每个团体中各选一名成员，组成一个 n 人的超级乐队。目标是让这个乐队中水平最高与最低的成员差距最小。请求出这个最小的可能差距。

解法思路：
这个问题可以巧妙地转化为一个滑动窗口问题。首先，将所有 n*m 个成员的信息（评分、所属团体编号）存入一个列表，并按评分从低到高进行排序。然后，问题就变成了在这个排好序的列表中，寻找一个最短的区间，这个区间内包含了来自所有 n 个不同团体的成员。这可以用经典的双指针（滑动窗口）技巧来解决：用一个指针（right）向右扩展窗口，直到窗口内集齐了所有团体的成员；然后，移动左指针（left）来收缩窗口，直到不再满足条件。在每次收缩前，都计算当前窗口的差距（members[right].score - members[left].score）并更新全局最小值。

------------------------------------

题目三：

题目大意：
在一个 n x m (1 <= n, m <= 50) 的迷宫中，有 k (1 <= k <= 5) 件古董和一个起点 'S'。迷宫中还有墙'#'和路'.'。移动会消耗时间。一个特殊的规则是：当你已经收集了 a 件古董后，每移动一步，所有未被收集的古董都会损失 a 点价值（价值最低降至1）。你需要规划一个收集所有 k 件古董的顺序，使得最终得到的总价值最高。

解法思路：
此题的核心突破口在于 k 的值非常小 (k <= 5)。这意味着所有可能的收集顺序数量 k! (最多 5! = 120) 是完全可以接受枚举的。因此，解法分为两步：首先，通过广度优先搜索（BFS）预计算出所有关键点（起点和 k 个古董位置）之间的两两最短路径长度。然后，枚举所有 k! 种排列组合作为收集顺序。对于每一种顺序，模拟整个过程：从起点出发，按顺序访问古董，在每次移动时，根据已收集的古董数量和移动的步数，更新所有尚未收集的古董的价值，并累加最终收集到的价值。最后在所有顺序中取最大值。

------------------------------------

题目四：

题目大意：
在一个长度为 n (1 <= n <= 100) 的一维地面上，有 m (1 <= m <= 1000) 个彩球从不同高度、不同时间开始下落。你需要控制一个筐来接球。每秒可以向左或向右移动一格，或不动。接到普通球得分，但接到陷阱球（积分为0）会被“冰冻”在原地3秒。在冰冻期间仍可接球，但无法移动。如果冰冻期内又接到陷阱球，冰冻时间重置为3秒。目标是获得最高总积分。

解法思路：
这是一个在时间和空间上进行的动态规划问题。首先，可以确定每个球的落地时间（=初始高度y + 开始下落时间t）。DP的状态可以设计为 `dp[time][pos][freeze]`，表示在 `time` 时刻，位于 `pos` 位置，且冰冻状态为 `freeze`（剩余冰冻秒数）时能获得的最大积分。状态转移则按时间顺序进行：`dp[t+1][...][...]` 的值由 `dp[t][...][...]` 转移而来。如果当前状态不是冰冻的（`freeze == 0`），则可以从 `pos-1`, `pos`, `pos+1` 三个位置转移过来；如果是冰冻的（`freeze > 0`），则只能从 `pos` 位置转移过来。在每个新位置，检查该时刻是否有球落下，加上其积分，并根据是否为陷阱球更新新的冰冻状态。