TikTok Spend it ALL OA 题解｜预算上万亿，循环购买如何跳过整圈

TikTok 的 Spend it ALL 历史 OA 题要求沿数组反复购买，预算却能达到 10¹⁵。逐次扣款会超时，直接把商品按价格排序又会改变答案。这篇只拆解这一道题；原帖未注明地区和整套试卷中的题号。

第一题：Spend it ALL 循环购买

题目描述

给定正整数价格数组 cost 和预算 B。从下标 0 扫到末尾，遇到买得起的商品就购买一次并扣款，否则跳过。到末尾后重新从 0 开始，直到一件也买不起，返回购买总次数。商品可以重复购买；n 不超过 2×10⁵，单价不超过 10⁹。自拟例子：cost=[6,4,3]，B=10。按原顺序先买 6，再买 4，共 2 次。如果排序成 [3,4,6]，则会买 3、4、3，共 3 次。因此排序不能代替题目规定的访问顺序。

解题思路

每轮先完整扫描当前数组，按规则实际扣款，同时记录本轮买到的商品数 k、总花费 S，并按原顺序留下这些商品。买不起的商品可以永久移除：预算只会下降，以后也买不起。若 k=0，结束。设扫描后还剩 b。留下的商品完整买一圈花 S，因此再跳过 q=b//S 个整圈，把 q×k 加入答案，预算更新为 b%S。然后对剩余列表重新扫描。除法发生在实际扫描之后，不能拿原数组总价强行套用到所有阶段。为什么扫描次数不会太多？设一轮开始时预算为 B₀。若 S>B₀/2，实际扫描后预算已小于一半；若 S≤B₀/2，整圈跳过后的余数小于 S，也小于一半。每轮都让预算至少减半，复杂度为时间 O(n log B)，保留列表需要 O(n) 空间。跳过整圈是安全的：被移除的商品已经永久买不起；只要预算覆盖留下商品的总价 S，就能依次买完这一圈。价格相同的两个下标仍是两件商品，不能用集合去重。预算、价格总和和答案均使用 64 位整数。

TikTok OA 练习如何验算

先写逐次购买的慢版本，用小预算随机对拍。再检查预算小于最低价、恰好买完一圈、所有价格相同，以及预算很大但只剩一件商品这几种输入。美国 Backend New Grad 的 Reddit 记录是 CodeSignal 四题；Taro 的 2024 年 1 月 Intern 记录则是两小时、两道选择题和三个函数实现。它们属于不同岗位测评，也没有把 Spend it ALL 列为题目。平台和时限以自己的邀请为准。

FAQ

一轮里跳过的商品，下轮还要试吗？

不用。跳过时已经买不起，后面的预算只会更少。

为什么不持续重复扣除整圈总价？

预算足够时可以一次除法跳过很多圈；不足一圈时，仍要按顺序扫描，判断哪些商品还能买。

最后只剩一件商品如何处理？

直接用剩余预算除以它的价格，加入购买次数即可。这也适合检查大预算是否溢出。

参考来源

LeetCode：TikTok Spend it ALL 题目讨论 Reddit：美国 Backend New Grad 的 CodeSignal OA Taro：美国 Intern 2024 年 1 月测评经历

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

微信：Coding0201
邮箱：[email protected]
Telegram：@OAVOProxy
WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。