一、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和重号IDduplicate。
代码实现细节
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和重号IDduplicate。
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 次跳跃。
-
代码的优化点：
-
滑动窗口的边界处理：
-
窗口的右边界 j 不能超过 n，否则会越界。
-
窗口的左边界 i 逐步向右移动，确保窗口长度最小。
-
-
时间复杂度：
-
滑动窗口的时间复杂度是 O(n)，因为每个石头最多被访问两次（一次扩展右边界，一次缩小左边界）。
-
这种方法在 n≤10**5 的规模下非常高效。
-
总结：
这段代码通过滑动窗口的方法，高效地找到了小青蛙的最小跳跃能力 y，使得它能够完成 2T 次往返跳跃。滑动窗口的核心思想是动态调整窗口的左右边界，确保窗口内的石头高度总和满足条件，同时找到最小的窗口长度 y。
![[Python爬虫系列]bilibili](https://i-blog.csdnimg.cn/direct/4d42d7e362f04d619f568f7885a850cd.png)
