技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

CC蓝桥杯算法真题打卡Day3

 收录于 蓝桥杯
   约 3603 字   预计阅读 8 分钟 
https://bing.ee123.net/img/rand?artid=146062922
目录

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

一、

https://i-blog.csdnimg.cn/direct/2671f8eb3f1442a7a4a5cdfbb6f37408.png

算法代码：

#include
using namespace std;
int main() {
int N;
cin >> N; // 读取数据行数
unordered_map idCount; // 用于统计每个ID出现的次数
vector 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 统计每个ID出现的次数。
  • 使用 vector 存储所有ID，方便后续排序。

​ 2. 读取所有ID

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

​ 3. 排序

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

​ 4. 查找重号

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

​ 5. 查找断号

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

​ 6. 输出结果

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

​ 代码实现细节

​ 1. 头文件

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

​ 2. 主函数

int main() {
int N;
cin >> N;
  • 读取数据行数 N 。

​ 3. 数据存储

unordered_map idCount;
vector ids;
int num;
  • unordered_map idCount ：用于统计每个ID出现的次数。
  • vector 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 ids 中。
  • 使用 unordered_map idCount 统计每个ID出现的次数。
  • 当遇到换行符 \n 时，结束当前行的读取。

​ 5. 排序

sort(ids.begin(), ids.end());
  • 对 vector ids 进行排序，方便后续查找断号和重号。

​ 6. 查找重号

int missing = -1, duplicate = -1;
for (auto& pair : idCount) {
if (pair.second == 2) {
duplicate = pair.first;
break;
}
}
  • 遍历 unordered_map 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 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 
#include 
using namespace std;
int main() {
int N;
cin >> N; // 读取数据行数
unordered_set 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 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;
}

二、

https://i-blog.csdnimg.cn/direct/e38375766ad84b7fb1578166faee4176.png

算法代码：

#include 
#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 逐步向右移动，确保窗口长度最小。

  1. 时间复杂度 ：

  • 滑动窗口的时间复杂度是 O(n)，因为每个石头最多被访问两次（一次扩展右边界，一次缩小左边界）。
  • 这种方法在 n≤10**5 的规模下非常高效。

总结：

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

更新于 2025-03-06
 蓝桥杯, 算法, C, C
返回 | 主页