小美的数组询问
美团 2024-03-09 春招笔试编程题
题目描述
小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 表示）。 现在小美想知道：如果那些未知元素在区间 [l, r] 内随机取值， 数组所有元素之和的最小值和最大值分别是多少？共有 q 次询问。
输入格式
第一行两个正整数 n、q，代表数组大小和询问次数。 第二行 n 个整数 a[i]，其中 a[i] = 0 表示该元素未知。 接下来 q 行，每行两个正整数 l、r，代表一次询问。
输出格式
输出 q 行，每行两个正整数，代表数组元素之和的最小值和最大值。
示例
示例 1
输入：
3 2
1 0 3
1 2
4 4
输出：
5 6
8 8
说明：
只有第二个元素未知。第一次询问范围 [1,2]，最小和 1+1+3=5、最大和 1+2+3=6；
第二次询问固定为 4，元素和必然为 1+4+3=8。
解题思路
第一步：把「未知元素」和「已知元素」分开
已知元素无论怎么问都不会变，它们的和 base 可以预处理一次；
未知元素有 cnt 个。
第二步：未知元素取边界就是极值
每个未知元素都在 [l, r] 里取整数，那么要让总和最小就都取 l，
要让总和最大就都取 r：
最小值 = base + cnt * l
最大值 = base + cnt * r
第三步：直接回答每次询问
每次询问只做一次乘法和加法，O(1)。千万不要每次都重新遍历数组 — 那样是 O(nq)，会超时。
完整代码实现
算法可视化 · 逐帧回放这道题的代码29 帧 · 录制输入
import sys
def solve() -> None:
"""已知和 + 未知个数 × 边界"""
data = sys.stdin.read().split()
if not data:
return
idx = 0
n = int(data[idx]); q = int(data[idx + 1]); idx += 2
base = 0
cnt = 0
for _ in range(n):
v = int(data[idx]); idx += 1
if v == 0:
cnt += 1
else:
base += v
out = []
for _ in range(q):
l = int(data[idx]); r = int(data[idx + 1]); idx += 2
out.append(f"{base + cnt * l} {base + cnt * r}")
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()
示例推演
数组 [1, 0, 3]：base = 1 + 3 = 4，cnt = 1。
| 询问 | l | r | 最小值 = 4+1·l | 最大值 = 4+1·r |
|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 6 |
| 2 | 4 | 4 | 8 | 8 |
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每次询问重新求和 | O(nq) | O(1) | 超时 |
| 预处理 + O(1) 回答 | O(n + q) | O(1) | 推荐 |
易错点总结
1. 把 0 当成真实元素
0 在这里是「未知」的占位符，不是数组里真的有个 0，
所以它既不能计入 base，也要单独统计个数。
2. 每次询问都重新遍历
base、cnt 与 l、r 无关，只需预处理一次。
3. 边界可能相等
当 l == r 时最小值等于最大值，这是合法情况，不用特判。
扩展思考
- 若题目要求输出「和的所有可能取值个数」，就要考虑不同取值的组合去重。
- 「未知元素在区间内取值」这类题的本质是线性函数取端点， 极值一定出现在边界上。