题目重点：Coding 题目限定只选一种查询、可无限重复；按各类型耗时和单次收益计算完整运行次数，区分整数次数与收益率近似。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每类查询有唯一名称、正整数运行分钟数和非负整数单次收益；一次查询必须完整执行才产生收益，不允许并行或中途换类型。
- 时间预算 K 为非负整数；并列最大收益按名称字典序选，空类型返回 (0,None)。这些数据形式和并列规则是训练约定。
解题路线
- 对每一类计算可完整执行次数 floor(K/duration)，再乘单次收益；取最大收益并保留类型。
- 不要仅比较 reward/duration：K=10 时 A 用 6 分钟赚 9，B 用 5 分钟赚 8，收益率 A 较高，但 A 总赚 9、B 总赚 16。
- 无论剩余时间多少都不能换其他查询类型，因为原题限定只选一种；如允许混搭，才转为背包或更复杂的排程问题。
- 用独立的逐分钟可执行起点枚举作为随机参考，对 10,000 组类型与预算比对。
手动走一遍
K=10，A 每次 6 分钟得 9，B 每次 5 分钟得 8。A 只能做一次收益 9，B 可做两次收益 16，返回 (16,'B')；不能按 9/6 大于 8/5 选 A。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training contract: choose one query type, repeat it within a time budget."""
def best_query_type(query_types: list[tuple[str, int, int]], minutes: int) -> tuple[int, str | None]:
if minutes < 0:
raise ValueError("minutes must be nonnegative")
best_profit = 0
best_name = None
names = set()
for name, duration, reward in query_types:
if name in names:
raise ValueError("duplicate query type")
names.add(name)
if duration <= 0 or reward < 0:
raise ValueError("duration must be positive and reward nonnegative")
profit = (minutes // duration) * reward
if profit > best_profit or (profit == best_profit and (best_name is None or name < best_name)):
best_profit, best_name = profit, name
return best_profit, best_name
复杂度
n 类查询各做常数次整数运算，时间 O(n)，保存名称去重集合 O(n)；若输入保证名称唯一，可仅用 O(1) 额外空间。
易错点与追问
容易失分的边界
- 用浮点单位时间收益率排序，忽略 floor(K/d) 的整数损耗。
- 剩余分钟改跑第二种类型，违反单一类型限制。
- 把 d>K 的查询算作可赚一次。
- 没有定义零耗时、负收益或最大收益并列时的行为。
继续深挖
- 如果允许查询并行，共享 CPU/内存资源如何约束？
- 如果允许混合查询类型，何时成为无界背包，何时需要考虑启动成本？
- 如果收益与运行次数相关并有递减效用，贪心是否仍成立？
