华为非AI方向机考10月14日笔试题与解析

《面试题目》

1. 落选加价成交额（150 分）：证券交易所里，买进与卖出两方递出的委托单，要依照开价高低和递单早晚完成配对，配上了才记入成交。本所执行的配对办法如下：

   • 买方配对办法：买方委托单按递出的先后逐笔进入配对。选中的卖方，开价不得超过这位买方的出价，而且要和该出价隔得最近。倘若卖方开价全部高于这位买方的出价，这位买方的委托单就先跳过。
   • 卖方权益：若仍有开价比本笔成交价更便宜的卖方委托单，只因隔得更远而本轮未被挑中，这些未被挑中的低开价卖方委托单可以把开价上调，每错过一轮上调 20 元。
   • 配对数量：双方按手数更少的一边成交，尚未配对的剩余手数留到后一轮继续（后一轮一样要执行上面第 2 条）。
   • 补充说明：卖方权益还有一类错过但不许上调的情形——两笔卖方开价相同，没被挑中的那笔同价卖方委托单不许上调。多笔开价并列且都是当前最高时，取更早递出的那一笔。
   • 要求：求出最终计入的成交额，即每笔配对成功的「开价乘以手数」全部累加。

   输入描述：第 1 行一个整数 step，表示每错过一轮的上调幅度（题目描述中的「20 元」即对应此值）；第 2 行一个整数 n，表示卖方笔数；接下来 n 行每行两个整数 price qty，表示卖方委托单的开价与手数；接下来 1 行一个整数 m，表示买方笔数；接下来 m 行每行两个整数 price qty，表示买方委托单的出价与手数。

   输出描述：输出一个整数，表示最终计入的成交额；成交额可能远超 64 位有符号整数。

   样例输入：20，3，100 10，80 5，60 3，2，90 8，100 5（自上而下依次为 step、卖方笔数及每笔的开价与手数、买方笔数及每笔的出价与手数）；样例输出：1140。

2. 脉冲后序右侧和（150 分）：外星通讯塔用一串互不相同的正整数强度发送信息，这些强度按二叉排序树组织以加快检索，接收端拿到的记录是这棵树的后序遍历；宇宙射线会把记录弄乱，于是它未必还能还原成合法的二叉排序树。需要完成两个部分：

   • 校验：判断这段强度能否当作某棵合法二叉排序树的后序遍历。
   • 解码：若能够还原，再求出这座塔「右缘轮廓」上的强度总和。右缘轮廓是从树的右侧望过去，每一层最后映入眼帘的那个结点（也就是该层最靠右的结点）所带的强度。
   • 输出：能还原时写下右缘轮廓的强度总和，不能还原时记成 -1。

   输入描述：一行若干个互不相同的正整数，用空格隔开，表示整段强度（即二叉树的后序遍历序列）；序列长度 m ≤ 10000，单个强度不超过 10⁹。

   输出描述：能还原时输出右缘轮廓的强度总和，不能还原时输出 -1。

   样例：输入 3 10 8 5，输出 23；输入 3 1 2，输出 -1；输入 1 2 3，输出 6。

《参考解析》

第 1 题 落选加价成交额：按题面规则逐步模拟

这题没有比模拟更省事的路子，关键是别把「上调」的时机搞错。买方委托按递出顺序逐笔处理，一笔买方的手数如果一次配不完，就继续进入下一轮，直到手数用完或者已经没有开价不超过其出价的卖方，此时剩余手数作废，直接换下一笔买方。

每一轮的挑选规则是：在「仍有手数、且开价不超过出价」的卖家里取开价最高的那一笔。开价并列且并列者都属当前最高时取更早递出的那笔——实现上从左往右扫描，只在遇到严格更高的开价时才更换当前选择，同价自然保留更早的那一笔，不需要额外记录时间戳。

成交价就是选中卖方的开价，成交手数取买方剩余手数与卖方剩余手数的较小值，把「成交价 × 成交手数」累加进总额并扣减卖方手数。一轮收尾时，给所有仍有手数、且开价严格低于本笔成交价的卖方加上 step：与成交价相等的同价委托单不许上调，开价高于成交价的也不动。

轮数是有上界的：一轮结束后，要么当前买方手数归零（这笔买方结束），要么至少有一笔卖方手数归零，所以总轮数不超过 n + m，每轮扫一遍卖方，时间复杂度 O(n(n+m))，空间 O(n+m) 保存两边委托单。最后注意成交额会超出 64 位有符号整数范围，必须用 __int128、BigInteger 或 Python 任意精度整数累加，并自己实现大整数的换行输出。

第 2 题 脉冲后序右侧和：单调栈校验并与层号配合求右视图

后序遍历的最后一个元素一定是根；二叉排序树要求左子树的值全部小于根、右子树的值全部大于根，所以判定与建树可以合并成一次从右往左的扫描。栈里维护的是当前还没向左分叉的「右脊」，其值自栈底向栈顶递减。给每个结点记一个允许区间 (low, high)，根取 (0, 10¹⁸) 即可（强度都是正整数）。

扫描到 val 时，把栈中所有值大于 val 的结点弹出，最后一个弹出的结点就是它的父结点：val 比这些祖先都小，只能挂在最深那个祖先的左侧，同时要求 low[父] < val < 父值，否则这段记录非法、直接输出 -1。如果一个都没弹出，说明栈顶比 val 小，val 就是栈顶的右孩子，要求 栈顶值 < val < high[栈顶]。挂好后继承区间——做左孩子时上界收紧为父值、下界取父的下界；做右孩子时下界抬高为父值、上界取父的上界——再把 val 压栈。每个下标最多进出栈各一次，时间与空间都是 O(m)。

校验通过后求右缘轮廓：按先右后左的顺序遍历，用显式栈携带层号，某一层第一次访问到的结点就是该层最靠右的结点，把它的强度累加即可。用显式栈是为了避开树退化成链（如递增序列）时递归过深。总和可能超过 32 位整数上限，要用 64 位。序列只有一个元素时循环不执行，右缘就是它自己。样例 3 10 8 5 还原出根 5、左孩子 3、右孩子 8（10 是 8 的右孩子），逐层最右为 5、8、10，和为 23，与输出一致。