C/C++蓝桥杯算法真题打卡（Day3）

一、P8598 [蓝桥杯 2013 省 AB] 错误票据 - 洛谷

算法代码：

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

int main() {
    int N;
    cin >> N;  // 读取数据行数
    unordered_map<int, int> idCount;  // 用于统计每个ID出现的次数
    vector<int> ids;                  // 用于存储所有ID（方便排序）
    int num;

    // 读取所有ID
    for (int i = 0; i < N; i++) {
        while (cin >> num) {
            ids.push_back(num);  // 将ID存入vector
            idCount[num]++;      // 统计ID出现的次数
            if (cin.get() == '\n') break;  // 换行时结束当前行的读取
        }
    }

    // 对ID进行排序
    sort(ids.begin(), ids.end());

    int missing = -1, duplicate = -1;  // 断号ID和重号ID

    // 查找重号
    for (auto& pair : idCount) {
        if (pair.second == 2) {
            duplicate = pair.first;  // 找到重号
            break;
        }
    }

    // 查找断号
    for (int i = ids[0]; i <= ids.back(); i++) {
        if (idCount.find(i) == idCount.end()) {
            missing = i;  // 找到断号
            break;
        }
    }

    // 输出结果
    cout << missing << " " << duplicate << endl;

    return 0;
}

代码思路

​1. 输入处理

• 读取数据行数 N。
• 使用 unordered_map<int, int> 统计每个ID出现的次数。
• 使用 vector<int> 存储所有ID，方便后续排序。

​2. 读取所有ID

• 使用 while (cin >> num) 逐行读取ID，直到遇到换行符 \n 结束当前行的读取。
• 将每个ID存入 vector<int> ids 中，并在 unordered_map<int, int> idCount 中统计其出现次数。

​3. 排序

• 对 vector<int> ids 进行排序，方便后续查找断号和重号。

​4. 查找重号

• 遍历 unordered_map<int, int> idCount，找到出现次数为2的ID，即为重号。

​5. 查找断号

• 从最小ID（ids[0]）到最大ID（ids.back()）遍历，检查每个ID是否在 unordered_map<int, int> idCount 中。
• 如果某个ID不在 unordered_map 中，则说明它是断号。

​6. 输出结果

• 输出断号ID missing 和重号ID duplicate。

​代码实现细节

​1. 头文件

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

• 使用万能头文件 bits/stdc++.h，包含所有标准库。
• 使用 using namespace std，避免每次调用标准库时需要写 std::。

​2. 主函数

int main() {
    int N;
    cin >> N;

• 读取数据行数 N。

​3. 数据存储

unordered_map<int, int> idCount;
vector<int> ids;
int num;

• unordered_map<int, int> idCount：用于统计每个ID出现的次数。
• vector<int> ids：用于存储所有ID，方便后续排序。

​4. 读取所有ID

for (int i = 0; i < N; i++) {
    while (cin >> num) {
        ids.push_back(num);
        idCount[num]++;
        if (cin.get() == '\n') break;
    }
}

• 逐行读取ID，存入 vector<int> ids 中。
• 使用 unordered_map<int, int> idCount 统计每个ID出现的次数。
• 当遇到换行符 \n 时，结束当前行的读取。

​5. 排序

sort(ids.begin(), ids.end());

• 对 vector<int> ids 进行排序，方便后续查找断号和重号。

​6. 查找重号

int missing = -1, duplicate = -1;
for (auto& pair : idCount) {
    if (pair.second == 2) {
        duplicate = pair.first;
        break;
    }
}

• 遍历 unordered_map<int, int> idCount，找到出现次数为2的ID，即为重号。

​7. 查找断号

for (int i = ids[0]; i <= ids.back(); i++) {
    if (idCount.find(i) == idCount.end()) {
        missing = i;
        break;
    }
}

• 从最小ID（ids[0]）到最大ID（ids.back()）遍历，检查每个ID是否在 unordered_map<int, int> idCount 中。
• 如果某个ID不在 unordered_map 中，则说明它是断号。

​8. 输出结果

cout << missing << " " << duplicate << endl;

• 输出断号ID missing 和重号ID duplicate。

​9. 返回

return 0;

• 程序正常结束。

​示例运行

​输入

2
7 9
5 6 8 11 9

​输出

10 9

​总结

• 代码通过 unordered_map 统计ID出现次数，结合排序和遍历，高效地找到断号和重号。
• 时间复杂度为 O(n)，其中 n 是ID的总数。
• 代码逻辑清晰，适合处理题目描述中的场景。

还有另一种形式（不排序，直接使用哈希表）：

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int N;
    cin >> N;  // 读取数据行数
    unordered_set<int> idSet;  // 用于存储所有ID
    int minID = INT_MAX, maxID = INT_MIN;  // 记录最小ID和最大ID
    int num;

    // 读取所有ID
    for (int i = 0; i < N; i++) {
        while (cin >> num) {
            idSet.insert(num);  // 将ID存入哈希表
            minID = min(minID, num);  // 更新最小ID
            maxID = max(maxID, num);  // 更新最大ID
            if (cin.get() == '\n') break;  // 换行时结束当前行的读取
        }
    }

    int missing = -1, duplicate = -1;  // 断号ID和重号ID

    // 查找重号
    unordered_set<int> seen;
    for (int id : idSet) {
        if (seen.count(id)) {
            duplicate = id;  // 找到重号
            break;
        }
        seen.insert(id);
    }

    // 查找断号
    for (int i = minID; i <= maxID; i++) {
        if (idSet.find(i) == idSet.end()) {
            missing = i;  // 找到断号
            break;
        }
    }

    // 输出结果
    cout << missing << " " << duplicate << endl;

    return 0;
}

二、P8775 [蓝桥杯 2022 省 A] 青蛙过河 - 洛谷 

算法代码： 

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

int n, T, h[N], ans;

int main() {
    // 读取河的宽度 n 和需要去学校的天数 T
    scanf("%d%d", &n, &T);
    // 将 T 乘以 2 得到实际过河的次数
    T <<= 1;
    
    // 读取每块石头的高度
    for (int i = 1; i < n; ++i) scanf("%d", &h[i]);
    
    // 使用滑动窗口的方法来找到满足条件的最小跳跃能力
    for (int i = 1, j = 0, sum = 0; i < n; i++) {
        // 扩展窗口的右边界，直到累加的高度大于等于 T
        while (j < n && sum < T) sum += h[++j];
        
        // 记录当前窗口的长度，即跳跃能力
        ans = max(ans, j - i + 1);
        
        // 缩小窗口的左边界，减去左边石头的高度
        sum -= h[i];
    }
    
    // 输出满足条件的最小跳跃能力
    printf("%d\n", ans);
    
    return 0;
}

规律：

        对于一个跳跃能力 y，青蛙能跳过河 2x 次，当且仅当对于每个长度为 y 的区间，这个区间内 h 的和都大于等于 2x

        这个问题涉及到对青蛙跳跃能力和石头高度分布的分析。我们需要理解为什么对于一个跳跃能力 y，青蛙能够跳过河 2x次，当且仅当对于每个长度为 y 的区间，这个区间内石头高度 h 的和都大于等于 2x。

1. 问题背景

• 青蛙需要往返 2x 次，每次跳跃必须落在石头或岸上。

• 每块石头的高度 h[i]表示这块石头可以被踩的次数。

• 跳跃能力 y 表示青蛙一次跳跃的最大距离。

2. 跳跃能力 y 的含义

• 如果青蛙的跳跃能力是 y，那么它每次跳跃的距离不能超过 y。

• 这意味着青蛙在跳跃时，只能选择距离当前位置不超过 y 的石头。

3. 为什么需要每个长度为 y 的区间和 ≥2x

• 必要性：

  • 如果存在一个长度为 y的区间，其石头高度和 <2x，那么青蛙在这个区间内无法完成 2x 次跳跃。

  • 因为青蛙每次跳跃必须落在石头上，而石头的高度限制了可以被踩的次数。

  • 如果某个区间的石头高度和不足 2x，青蛙在这个区间内无法完成足够的跳跃次数。

• 充分性：

  • 如果每个长度为 y 的区间的石头高度和 ≥2x，那么青蛙可以在每个区间内完成足够的跳跃次数。

  • 因为青蛙的跳跃能力是 y，它可以在每个区间内自由选择石头进行跳跃，而不会受到石头高度不足的限制。

4. 具体分析

• 青蛙的跳跃路径：

  • 青蛙需要从起点跳到终点，再跳回起点，重复 x 次。

  • 每次跳跃的距离不能超过 y。

• 区间的划分：

  • 将河分成若干个长度为 y 的区间。

  • 每个区间内的石头高度和必须≥2x，因为青蛙需要在这些区间内完成 2x2x 次跳跃。

• 石头高度的作用：

  • 每块石头的高度 h[i] 表示这块石头可以被踩的次数。

  • 如果某个区间的石头高度和<2x，那么青蛙在这个区间内无法完成 2x 次跳跃。

5. 举例说明

假设：

• 河的宽度 n=5。

• 需要去学校的天数 x=1，实际过河次数 2x=2。

• 石头高度 h=[3,1,2,1]。

跳跃能力 y=2：

• 区间划分：

  • 区间 1: 位置 1 和 2，高度和 3+1=4≥2。

  • 区间 2: 位置 2 和 3，高度和 1+2=3≥2。

  • 区间 3: 位置 3 和 4，高度和 2+1=3≥2。

• 每个区间的石头高度和都 ≥2，因此青蛙可以完成 2 次跳跃。

跳跃能力 y=1：

• 区间划分：

  • 区间 1: 位置 1，高度和 3≥2。

  • 区间 2: 位置 2，高度和 1<2。

  • 区间 3: 位置 3，高度和 2≥2。

  • 区间 4: 位置 4，高度和 1<2。

• 存在区间的石头高度和 <2，因此青蛙无法完成 2 次跳跃。

6. 总结

• 对于一个跳跃能力 y，青蛙能够跳过河 2x 次，当且仅当对于每个长度为 y 的区间，这个区间内石头高度 h 的和都大于等于 2x。

• 这是因为青蛙的跳跃能力限制了它每次跳跃的距离，而石头的高度限制了它可以在每块石头上踩的次数。

• 如果某个区间的石头高度和不足2x，青蛙在这个区间内无法完成足够的跳跃次数。

• 如果每个区间的石头高度和都 ≥2x，青蛙可以在每个区间内自由选择石头进行跳跃，完成 2x次跳跃。

代码思路：

这段代码的目的是通过滑动窗口的方法，找到小青蛙的最小跳跃能力 y，使得它能够完成 2x 次往返跳跃。以下是代码的详细思路：

1. 输入处理

• 读取河的宽度 n 和需要去学校的天数 T：

  • 使用 scanf("%d%d", &n, &T); 读取输入。

  • 河的宽度 n 表示从起点到终点共有 n 个位置（包括起点和终点）。

  • T 是小青蛙需要去学校的天数，实际过河次数是 2T（往返各一次）。

• 将 T乘以 2：

  • 使用 T <<= 1; 将 T左移一位，相当于 T=2T，表示实际过河次数。

2. 读取石头高度

• 读取每块石头的高度：

  • 使用 for (int i = 1; i < n; i++) scanf("%d", &h[i]); 读取每块石头的高度。

  • 数组 h 的下标从 1 开始，表示从起点到终点之间的 n−1块石头的高度。

  • h[i]表示距离起点 i的位置的石头高度。

3. 滑动窗口寻找最小跳跃能力

• 初始化滑动窗口：

  • 使用 for (int i = 1, j = 0, sum = 0; i < n; ++i) 初始化滑动窗口。

  • i是窗口的左边界，表示当前跳跃的起点。

  • j是窗口的右边界，表示当前跳跃的终点。

  • sum 是窗口内石头高度的累加和。

• 扩展窗口的右边界：

  • 使用 while (j < n && sum < T) sum += h[++j]; 扩展窗口的右边界。

  • 不断将右边界 j向右移动，累加石头的高度，直到累加的高度 sum大于等于 T。

  • 这一步的目的是找到一个窗口，使得窗口内的石头高度总和足够支持 2T 次跳跃。

• 记录窗口的长度：

  • 使用 ans = max(ans, j - i + 1); 记录当前窗口的长度。

  • 窗口的长度 j−i+1表示当前跳跃能力 y。

  • 通过取最大值，确保找到最小的跳跃能力。

• 缩小窗口的左边界：

  • 使用 sum -= h[i]; 缩小窗口的左边界。

  • 将左边界 i 向右移动，减去左边石头的高度，继续寻找更小的跳跃能力。

4. 输出结果

• 输出满足条件的最小跳跃能力：

  • 使用 printf("%d\n", ans); 输出结果。

  • ans 是满足条件的最小跳跃能力 yy。

代码的核心思想：

• 滑动窗口：

  • 通过滑动窗口的方法，动态调整窗口的左右边界，找到一个最小的窗口长度 y，使得窗口内的石头高度总和至少为 T。

  • 窗口的长度 y 表示小青蛙的跳跃能力。

• 跳跃能力的定义：

  • 跳跃能力 y 表示小青蛙一次跳跃的最大距离。

  • 通过滑动窗口找到的 y是最小的跳跃能力，使得小青蛙能够完成 2T 次跳跃。

代码的优化点：

1. 滑动窗口的边界处理：

   • 窗口的右边界 j 不能超过 n，否则会越界。

   • 窗口的左边界 i 逐步向右移动，确保窗口长度最小。

2. 时间复杂度：

   • 滑动窗口的时间复杂度是 O(n)，因为每个石头最多被访问两次（一次扩展右边界，一次缩小左边界）。

   • 这种方法在 n≤10**5 的规模下非常高效。

总结：

这段代码通过滑动窗口的方法，高效地找到了小青蛙的最小跳跃能力 y，使得它能够完成 2T 次往返跳跃。滑动窗口的核心思想是动态调整窗口的左右边界，确保窗口内的石头高度总和满足条件，同时找到最小的窗口长度 y。