Moe's CF Life

喵哈喽~！各位小伙伴们，今天由我来给大家讲解一道非常可爱的入门题目——Rudolf and the Ticket！这道题就像帮朋友挑礼物一样简单有趣，让我们一起来看看吧，喵~

题目大意

这道题是说，有一个叫 Rudolf 的朋友要去见 Bernard，他需要坐地铁。地铁的自动售票机很特别哦，它只接受 正好两枚硬币，而且这两枚硬币的面值加起来 不能超过 k。

Rudolf 有两个口袋：

左边口袋里有 n 枚硬币，面值分别是 b1, b2, ..., bn。
右边口袋里有 m 枚硬币，面值分别是 c1, c2, ..., cm。

他需要从左边口袋里选一枚，再从右边口袋里选一枚，然后把这两枚硬币投进售票机。

我们的任务就是帮 Rudolf 计算一下，总共有多少种不同的选择方法（即多少种硬币对），可以满足 b[i] + c[j] <= k 这个条件呢？

简单来说，就是从左口袋选一个数，从右口袋选一个数，有多少种配对方式使得它们的和不大于 k，喵~

题解方法

看到这个问题，是不是觉得很简单呀？就像猫猫我有两堆小鱼干，一堆是金枪鱼味的，一堆是三文鱼味的，我想知道每次各拿一根，有多少种组合不会让我吃得太撑（不超过k）！

最直接的方法就是把所有可能的组合都试一遍嘛！这种方法我们称之为 暴力枚举 (Brute Force)。

具体步骤是这样的：

我们先从左边的口袋里拿出一枚硬币 b[i]。
然后，我们用这枚硬币去和右边口袋里的 每一枚 硬币 c[j] 进行配对。
每配对一次，我们就计算一下它们的和 b[i] + c[j]。
判断这个和是不是小于等于 k。如果是，那这就是一种可行的方法，我们就把计数器加一。
当我们把左边口袋里的第一枚硬币和右边所有硬币都配对完后，就再从左边口袋里拿出第二枚硬币，重复上面的步骤。
直到左边口袋里的所有硬币都试过一遍，我们就得到了最终的答案啦！

为了实现这个过程，我们可以用两层循环（嵌套循环）：

外层循环遍历左口袋的 n 枚硬币。
内层循环遍历右口袋的 m 枚硬币。

因为题目给的数据范围很小 (n, m <= 100)，所以总共的计算次数最多也就是 100 * 100 = 10000 次，这对于电脑来说是小菜一碟，完全不会超时，所以这个简单直接的方法是完全可行的哦！

题解

下面就是这道题的 C++ 代码啦，我已经加上了可爱的注释，方便你理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 解决单个测试用例的函数喵~
void solve() {
    int n, m, k;
    // 喵，先读入 n, m, k 这三个重要的数字
    std::cin >> n >> m >> k;
    
    // 创建一个 vector 来存放左边口袋的 n 枚硬币
    std::vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }
    
    // 创建另一个 vector 来存放右边口袋的 m 枚硬币
    std::vector<int> c(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> c[i];
    }
    
    // 用一个 long long 类型的变量来记录合格的组合数量，以防万一数量太多 int 存不下啦
    long long valid_pairs = 0;
    
    // 开始暴力枚举！( •̀ ω •́ )✧
    // 外层循环，遍历左口袋的每一枚硬币
    for (int i = 0; i < n; ++i) {
        // 内层循环，遍历右口袋的每一枚硬币，和外面的 b[i] 配对
        for (int j = 0; j < m; ++j) {
            // 检查它们的和是不是小于等于 k
            if (b[i] + c[j] <= k) {
                // 如果是的话，这就是一种好方法！计数器+1！
                valid_pairs++;
            }
        }
    }
    
    // 所有组合都检查完啦，把答案打印出来就好
    std::cout << valid_pairs << '\n';
}

// 主函数，用来处理多个测试用例哦
int main() {
    // 这两行是加速输入输出的魔法，让程序跑得更快，不容易超时喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t; // 先读入有多少组测试
    while (t--) {
        solve(); // 循环调用 solve 函数解决每一组测试
    }
    
    return 0;
}

知识点介绍

这道题虽然简单，但它也包含了一些编程竞赛中非常基础和重要的知识点哦！

暴力枚举 (Brute Force)
- 这是一种解决问题的基本策略，就是通过尝试所有可能的解来找到答案。它简单、直观，容易实现。当问题的规模不大时（就像这道题的 n, m <= 100），暴力枚举通常是首选的有效方法。
嵌套循环 (Nested Loops)
- 嵌套循环是实现暴力枚举的常用工具。当我们需要从两个或多个集合中各取一个元素进行组合时，使用嵌套循环就非常自然。一个外层循环处理第一个集合，一个内层循环处理第二个集合，这样就能遍历所有 (元素1, 元素2) 的配对。
时间复杂度分析 (Time Complexity Analysis)
- 这是一个衡量算法效率的重要指标。对于这道题的解法，外层循环执行 n 次，内层循环在每次外层循环中执行 m 次，所以总的执行次数大约是 n * m 次。我们把这个记作 O(n*m)。了解时间复杂度可以帮助我们判断一个算法在给定的数据限制下是否会超时。

好啦，今天的讲解就到这里啦！是不是很简单呢？希望大家都能轻松掌握！下次再见啦，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍