分享两道 Microsoft OA 题目思路:服务器区间最短路径查询,以及相邻数值不能同时选择时的最大和问题。
Microsoft OA 题目解析:区间路径与最大和
整理 Microsoft OA 两道编程题:服务器区间最短路径查询与相邻元素不能同时选择的最大和问题,分享题意和解题思路。

Microsoft OA 题目分享
整理服务器区间路径查询与数组选数问题的核心思路,供复习参考。
Question 1:服务器区间最短路径查询
每个服务器只能往更近的邻居走。先预处理每个点的最近邻方向,存入 nb;再分别向右、向左维护前缀代价数组 rs 和 ls,代价按是否走最近邻加 1 或计算容量差。查询时用前缀数组相减,O(1) 得到结果。
Question 2:相邻数值不能同时选择
从数组里挑数,要求和尽量大,且相邻数值不能同时选。先统计每个数值的总和并排序。DP 维护两个状态 p、q,分别代表上上个和上个位置的最优值。当前数值如果和前一个相差 1,就在两种选择中取较大值;否则直接累加,最后返回 q。