美团校招机试 - 小美的数组询问（20240309-T2）

题目来源

美团校招笔试真题_小美的数组询问

题目描述

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。

现在小美想知道，如果那些未知的元素在区间 [l, r] 范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？

共有 q 次询问。

输入描述

第一行输入两个正整数 n, q，代表数组大小和询问次数。

• 1 ≤ n, q ≤ 10^5

第二行输入 n 个整数 ai，其中如果输入 ai 的为 0，那么说明 ai 是未知的。

• 0 ≤ ai ≤ 10^9

接下来的 q 行，每行输入两个正整数 l,r，代表一次询问。

• 1 ≤ l ≤ r ≤ 10^9

输出描述

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

用例

题目解析

本题需要注意题目这句话：

如果那些未知的元素在区间 [l, r] 范围内随机取值的话

这里的 [l, r] 区间就是取值区间，而不是a数组的范围区间。

即，题目希望我们将a数组中0元素替换为 [l, r] 区间内的数，而不是替换为a数组的[l, r]范围内的数。

因此，本题就是一个简单的问题了。具体逻辑直接看代码就行。

本题主要需要注意的是，整型溢出问题，以及大数量级输入读取问题。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    const [n, q] = (await readline()).split(" ").map(Number);

    let sum = 0;
    let countZero = 0;

    const a = (await readline()).split(" ").map(Number);
    for (let i = 0; i < n; i++) {
        if (a[i] == 0) {
            countZero++;
        }

        sum += a[i];
    }

    for (let i = 0; i < q; i++) {
        const [l, r] = (await readline()).split(" ").map(Number);

        const minSum = sum + countZero * l;
        const maxSum = sum + countZero * r;

        console.log(`${minSum} ${maxSum}`);
    }
})();

Java算法源码

Scanner 方式读取

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int q = sc.nextInt();

        long sum = 0;
        long countZero = 0;

        for (int i = 0; i < n; i++) {
            int ai = sc.nextInt();

            if (ai == 0) {
                countZero++;
            }

            sum += ai;
        }

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();

            long minSum = sum + countZero * l;
            long maxSum = sum + countZero * r;

            System.out.println(minSum + " " + maxSum);
        }
    }
}

BufferedReader 方式读取

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int q = Integer.parseInt(line[1]);

        long sum = 0;
        long countZero = 0;

        line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int ai = Integer.parseInt(line[i]);

            if (ai == 0) {
                countZero++;
            }

            sum += ai;
        }

        for (int i = 0; i < q; i++) {
            line = br.readLine().split(" ");
            int l = Integer.parseInt(line[0]);
            int r = Integer.parseInt(line[1]);

            long minSum = sum + countZero * l;
            long maxSum = sum + countZero * r;

            System.out.println(minSum + " " + maxSum);
        }
    }
}

 StreamTokenizer 方式读取

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        st.nextToken();
        int n = (int) st.nval;

        st.nextToken();
        int q = (int) st.nval;

        long sum = 0;
        long countZero = 0;

        for (int i = 0; i < n; i++) {
            st.nextToken();
            int ai = (int) st.nval;

            if (ai == 0) {
                countZero++;
            }

            sum += ai;
        }

        for (int i = 0; i < q; i++) {
            int l, r;

            st.nextToken();
            l = (int) st.nval;

            st.nextToken();
            r = (int) st.nval;

            long minSum = sum + countZero * l;
            long maxSum = sum + countZero * r;

            System.out.println(minSum + " " + maxSum);
        }
    }
}

Python算法源码

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    sumA = sum(a)
    zeroCount = a.count(0)

    for _ in range(q):
        l, r = map(int, input().split())

        minSum = sumA + zeroCount * l
        maxSum = sumA + zeroCount * r

        print(f"{minSum} {maxSum}")

C算法源码

#include <stdio.h>

int main() {
    int n, q;
    scanf("%d %d", &n, &q);

    long sum = 0;
    long zeroCount = 0;

    for (int i = 0; i < n; i++) {
        int ai;
        scanf("%d", &ai);

        if (ai == 0) {
            zeroCount++;
        }

        sum += ai;
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        scanf("%d %d", &l, &r);

        long minSum = sum + zeroCount * l;
        long maxSum = sum + zeroCount * r;

        printf("%ld %ld\n", minSum, maxSum);
    }

    return 0;
}

C++算法源码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    long sum = 0;
    long zeroCount = 0;

    for (int i = 0; i < n; i++) {
        int ai;
        cin >> ai;

        if (ai == 0) {
            zeroCount++;
        }

        sum += ai;
    }

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;

        long minSum = sum + zeroCount * l;
        long maxSum = sum + zeroCount * r;

        cout << minSum << " " << maxSum << endl;
    }

    return 0;
}