题目重点：Uber OA Purchase Optimization 完整题意：商品价格非递减、从指定摊位往右选购，在预算内最大化购买件数；用前缀和与二分逐查询求解。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- prices 按摊位顺序非递减且价格非负；每个查询的 pos 为 1-based 起点，amount 为非负预算，右侧每个摊位最多买一件。
- 可以跳过某个摊位继续往右访问；目标最大化购买件数，不要求把预算花完。
- 输出每个查询的最大件数，不返回具体购买的摊位；如果要求见证解，最便宜的前缀就是一组最优购买方案。
解题路线
- 由于后缀价格非递减，固定买 t 件时最便宜的一组必是从 pos 开始的 t 个摊位；任意跳过较便宜商品去买更贵商品都不会降低成本。
- 预计算前缀和 prefix。买后缀前 t 件的成本为 prefix[pos−1+t]−prefix[pos−1]，随 t 非递减。
- 对每个查询在前缀和数组中二分最远 end，使 prefix[end]≤prefix[pos−1]+amount，答案为 end−(pos−1)。
手动走一遍
prices=[3,4,5,5,7]：pos=2、预算10 时可买 4+5=9，买第三件至少14，因此答案2；pos=1、预算24 可买全部5件；pos=5、预算5 买不起售价7，答案0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Maximum purchases from a sorted-price suffix under each budget."""
from bisect import bisect_right
def max_purchases(prices: list[int], queries: list[tuple[int, int]]) -> list[int]:
if any(price < 0 for price in prices) or any(a > b for a, b in zip(prices, prices[1:])):
raise ValueError("prices must be nonnegative and nondecreasing")
prefix = [0]
for price in prices:
prefix.append(prefix[-1] + price)
answer = []
for pos, amount in queries:
if not 1 <= pos <= len(prices) or amount < 0:
raise ValueError("invalid position or budget")
start = pos - 1
# prefix[end] - prefix[start] is the cost of buying [start, end).
end = bisect_right(prefix, prefix[start] + amount, lo=pos, hi=len(prices) + 1) - 1
answer.append(end - start)
return answer
复杂度
预处理 O(n) 时间与空间；每个查询二分 O(log n)，q 个查询总时间 O(n+q log n)、空间 O(n+q)（含答案）。若价格无序，简单前缀和不再代表任意 t 件的最低成本。
易错点与追问
容易失分的边界
- 起点 pos 是 1-based，前缀起点应是 pos−1；二分结果是前缀 end 下标，不是商品下标。
- 价格相等或为 0 时前缀和不严格递增，使用 bisect_right 找到可负担的最远 end。
- 若题目禁止跳过摊位，因价格已非递减，最优件数仍相同；但无序价格时“可跳过”和“必须连续买”的答案不同。
继续深挖
- 若有退款或动态价格更新，静态前缀和失效；Fenwick/线段树可支持点更新与按前缀和定位，但必须保持价格排序约束。
- 若价格无序但允许任意挑商品，需对每个查询后缀寻找最便宜 t 件，不能直接沿摊位顺序二分前缀。
