小明和神秘宝箱问题解析

问题理解

小明有 $n$ 个神秘宝箱，每个宝箱 $i$ 可以得到的金币数在区间 $[l_i, r_i]$ 内。我们需要计算开启所有宝箱后，小明能够获得的最少金币数和最大金币数。

数学分析

这是一个简单的区间求和问题：

• 最少金币数：当每个宝箱都取最小值 $l_i$ 时，总金币数最小
• 最大金币数：当每个宝箱都取最大值 $r_i$ 时，总金币数最大

数学表达式为：

• 最少金币数：$\sum_{i=1}^{n} l_i$
• 最大金币数：$\sum_{i=1}^{n} r_i$

代码实现

#include<bits/stdc++.h>  // 包含常用标准库
using namespace std;

int main(){
    int n;  // 宝箱数量
    cin >> n;  // 读取宝箱数量
    
    // 初始化最少金币数和最大金币数
    long long minn = 0;  // 最少金币数，初始为0
    long long maxx = 0;  // 最大金币数，初始为0
    
    // 循环处理每个宝箱
    for(int i = 0; i < n; i++){
        long long l, r;  // 当前宝箱的最小值和最大值
        cin >> l >> r;   // 读取当前宝箱的区间
        
        minn += l;  // 累加最小值到最少金币数
        maxx += r;  // 累加最大值到最大金币数
    }
    
    // 输出结果：最少金币数 最大金币数
    cout << minn << " " << maxx;
    
    return 0;  // 程序正常结束
}

算法分析

1. 时间复杂度：$O(n)$，需要遍历所有 $n$ 个宝箱
2. 空间复杂度：$O(1)$，只使用了固定数量的变量

注意事项

• 使用 long long 类型存储结果，因为 $n$ 最大为100000，$l_i$ 和 $r_i$ 最大为 $10^9$，总和可能达到 $10^{14}$，超出了 int 类型的表示范围
• 算法简单直接，直接累加每个区间的端点是最高效的解决方案
• 题目保证 $1 \leq l_i \leq r_i \leq 10^9$，不需要额外的输入验证