【美团20240309笔试算法题】小美的数组询问

系列文章目录

【美团20240309笔试算法题】小美的MT

---

---

小美的数组询问

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

---

样例

输入：

• 第一行整数n和q，表示数组的长度和询问的次数;
• 第二行输入n个整数ai，其中如果输入ai的为 0，那么说明ai是未知的，接下来的q行，每行输入两个正整数l,r，代表一次询问。

3 2
1 0 3
1 2
4 4

输出：

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

5 6
8 8

---

分析

对于已知的元素，遍历的时候求和sum, 对于值为0的元素也就是未知的元素，用cnt记录下个数。这里给出了区间[l,r]，也就能知道区间最大值和最小值。所以所有元素的最大值就是sum + cnt * r ; 最小值就是sum + cnt * l

---

java参考代码

package org.example;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int q = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}//cnt计算0的个数int cnt = 0;//sum计算除0之外所有数字之和int sum = 0;for (int i = 0; i < n; i++) {if (a[i] == 0) {cnt++;}sum += a[i];}//最大值就是sum 加上 cnt + r 其中cnt是0的个数，r是区间最大值即随机数的最大值。最小值反之。for (int i = 0; i < q; i++) {int l = scanner.nextInt();int r = scanner.nextInt();System.out.println((sum + cnt * l) + " " + (sum + cnt * r));}}
}