顺丰 9.24 Java 笔试：矩形填充与最少加油次数

《面试题目》

1. 选择题（30 题，共 60 分）：单选与多选混合，覆盖面很广，含少量算法题。
2. 编程题一：给定一个 r×c 的矩形，用 1×2 和 2×2 两种小矩形去填充，判断能否恰好填满；若能，返回最少需要多少个小矩形。
3. 编程题二：给定路的总长度、初始油量，以及沿途各加油站的位置与可加油量，判断能否到达终点；若能，返回最少需要加几次油。

《参考解析》

矩形填充的最少块数（贪心）

块数最少等价于「让 2×2 的块尽可能多」。先看面积：r×c 为奇数时必然填不满，直接判不可行。面积为偶数时，若 r、c 都是偶数，可以整块用 2×2 铺满，答案是 r×c/4；若两者一奇一偶，奇数的那一维铺不下 2×2，最多只能覆盖 (r-1)×c 个格子用 2×2，余下一整行（长度为偶数）用 1×2 补齐，答案就是 (r-1)×c/4 + c/2。逐行贪心铺即可，不需要搜索。

这题有个非常典型的坑：r、c 本身可能不大，但面积与计数相乘仍会溢出 int，第一遍只过 80% 多的用例常常就出在这里——把参与乘法与累加的变量一律声明成 long，是交卷前最划算的一次检查。

最少加油次数：贪心 + 大顶堆

标准模型是「反悔贪心」。从起点往终点开，把沿途经过的加油站的可加油量全部压进一个最大堆；当剩余油量不足以走到下一个加油站（或终点）时，就从堆顶弹出最大的一次加油量，相当于反悔——假装刚才在那里加过油，加油次数加一，然后判断油量是否够用。堆为空仍走不到，说明到不了终点。

复杂度是 O(n log n)。如果写成「贪心加回溯」，通过率通常很低：暴力枚举「在哪些站加油」会随站点数指数膨胀，而堆把「选最大的那几次」这件事降成了对数级的取极值，这才是本题的预期解。

选择题的取舍

30 道客观题 60 分、单选多选混排，考的是知识面宽度而非深度，临场最容易卡在「见过但记不清细节」上。两道编程题都是标准贪心，40 分比在选择题上纠结更好拿，做题顺序上建议先拿编程题的分。