跳到主要内容

小美的数组询问

题目描述​

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

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

数组所有元素之和的最小值和最大值分别是多少？共有 q 次询问。

输入描述​

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

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

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

输出描述​

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

示例​

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

输出：
5 6
8 8

解释：
只有第二个元素是未知的。
第一次询问，数组最小的和是 1 + 1 + 3 = 5，最大的和是 1 + 2 + 3 = 6。
第二次询问，显然数组的元素和必然为 8。

解题思路​

核心思想： 将数组元素分为已知和未知两部分，分别计算贡献。

算法步骤：

  1. 预处理阶段：

    • 统计未知元素（值为0）的数量 unknownCount
    • 计算已知元素的总和 knownSum

  2. 查询处理：

    • 最小和：所有未知元素取最小值 l，总和 = knownSum + unknownCount × l
    • 最大和：所有未知元素取最大值 r，总和 = knownSum + unknownCount × r

时间复杂度：O(n + q)，空间复杂度：O(n)

C++ 解法​

#include <iostream>
#include <vector>

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

    int unknownCount = 0;
    long long knownSum = 0;
    std::vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
        if (arr[i] == 0) {
            unknownCount++;
        } else {
            knownSum += arr[i];
        }
    }

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

        long long minSum = knownSum + unknownCount * l;
        long long maxSum = knownSum + unknownCount * r;

        std::cout << minSum << " " << maxSum << std::endl;
    }
    return 0;
}