T1 小美的数组询问(15分) - 美团编程题 & 题解

考试平台： 牛客网

题目类型： 30道单选题（60分）+ 2 道编程题 （15分 + 25分）

考试时间： 2024-03-09 （两小时）

题目描述

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间 [l,r] 范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有q 次询问。

输入描述：

第一行输入两个正整数 n,q，代表数组大小和询问次数。
第二行输入n个整数 $a_i$，其中如果输入的 $a_i$ 为 0，那么说明 $a_i$ 是未知的。
接下来的q行，每行输入两个正整数 l,r，代表一次询问。
$1\le n,q\le 10^5$
$0\le a_i\le 10^9$
$1\le l\le r\le 10^9$

输出描述：

输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。

示例：

输入：
3 2
1 0 3
1 2
4 4

输出：
5 6
8 8

说明：
只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1=3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

题解

n, q = map(int, input().split())
a = list(map(int, input().split()))

tot = sum(a)
# 0 的个数
zero_cnt = sum([1 for v in a if v == 0])

for _ in range(q):
    l, r = map(int, input().split())
    # 最小和： 0 都选 l
    # 最大和： 0 都选 r
    min_sum, max_sum = tot + zero_cnt * l, tot + zero_cnt * r
    print(min_sum, max_sum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14