[蓝桥杯]青蛙过河
- 2025-10-19 21:32:39
青蛙过河
问题描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。
小青蛙一共需要去学校上 xx 天课, 所以它需要往返 2x2x 次。当小青蛙具有 一个跳跃能力 yy 时, 它能跳不超过 yy 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 xx 次课。
输入格式
输入的第一行包含两个整数 n,xn,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x2x 才是实际过河的次数。
第二行包含 n−1n−1 个非负整数 H1,H2,⋯,Hn−1H1,H2,⋯,Hn−1, 其中 Hi>0Hi>0 表示在河中与 小青蛙的家相距 ii 的地方有一块高度为 HiHi 的石头, Hi=0Hi=0 表示这个位置没有石 头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例输入
5 1
1 0 1 0
样例输出
4
样例说明
由于只有两块高度为 11 的石头，所以往返只能各用一块。第 11 块石头和对岸的距离为 44，如果小青蛙的跳跃能力为 33 则无法满足要求。所以小青蛙最少需要 44 的跳跃能力。
评测用例规模与约定
对于 30%30% 的评测用例, n≤100n≤100;
对于 60%60% 的评测用例, n≤1000n≤1000;
对于所有评测用例, 1≤n≤105,1≤x≤109,1≤Hi≤1041≤n≤105,1≤x≤109,1≤Hi≤104 。
运行限制
最大运行时间：1s最大运行内存: 512M
总通过次数: 5894 | 总提交次数: 7911 | 通过率: 74.5%
难度: 困难 标签: 2022, 贪心, 省赛, 二分
青蛙过河问题算法解析与实现
1. 问题分析
青蛙需要往返河岸 2x 次（x 为上学天数），每次跳跃距离不超过跳跃能力 y。河中有 n−1 个位置（从 1 到 n−1）可能有石头，每个石头有初始高度 Hi。青蛙落在石头上会使高度减 1，高度为 0 时不可再落。目标是找到最小跳跃能力 y，使得青蛙能完成 2x 次过河。
关键观察：
当 y≥n 时，青蛙可直接从起点跳到终点，不使用石头，始终可行。当 y 2. 算法思路 使用 二分查找 确定最小 y，并通过 前缀和 高效检查区间和条件： 二分框架：在 [1,n] 范围内搜索 y。检查函数：对每个候选 y： 若 y≥n，直接返回 true。否则，检查每个长度为 y 的连续石头子数组的总高度 ≥2x。 前缀和优化：预处理石头高度前缀和，实现 O(1) 的区间和查询。 3. 算法步骤 graph TD A[开始] --> B[读取输入 n, x 和石头高度数组 arr] B --> C[计算总需求 total = 2*x] C --> D[构建前缀和数组 prefix] D --> E[二分查找初始化 left=1, right=n] E --> F{left <= right} F -- 是 --> G[mid = (left+right)/2] G --> H[调用 check(mid)] H --> I{y >= n?} I -- 是 --> J[返回 true] I -- 否 --> K{石头区间和 >= total?} K -- 所有区间满足 --> L[返回 true] K -- 任一区间不满足 --> M[返回 false] L --> N[记录 ans=mid, right=mid-1] M --> O[left=mid+1] N --> F O --> F F -- 否 --> P[输出 ans] P --> Q[结束] 4. C++ 代码实现 #include #include #include using namespace std; bool check(int y, long long need, vector if (y >= n) return true; // 直接跳到对岸，无需石头 int L = n - 1; // 石头位置数量 if (L == 0) return false; // 无石头且 y < n，不可行 if (y > L) { // 区间大于石头数，检查全部石头 return prefix[L] >= need; } for (int i = 0; i <= L - y; i++) { long long sum_interval = prefix[i + y] - prefix[i]; if (sum_interval < need) return false; } return true; } int main() { int n; long long x; cin >> n >> x; long long total_needed = 2 * x; vector for (int i = 0; i < n - 1; i++) { cin >> arr[i]; } // 处理边界情况：河宽为 0 if (n == 0) { cout << 0 << endl; return 0; } // 构建前缀和数组 vector for (int i = 0; i < arr.size(); i++) { prefix[i + 1] = prefix[i] + arr[i]; } // 二分查找最小 y int left = 1, right = n; int ans = n; while (left <= right) { int mid = left + (right - left) / 2; if (check(mid, total_needed, prefix, n)) { ans = mid; right = mid - 1; } else { left = mid + 1; } } cout << ans << endl; return 0; } . 代码解析 输入处理：读取河宽 n、天数 x 和石头高度数组 arr。前缀和数组：prefix[i] 表示前 i 个石头的高度和，用于快速计算区间和。检查函数： y >= n 时直接返回 true。对每个起点 i，计算区间 [i, i+y-1] 的石头和，若任一区间和 < 2x 则返回 false。 二分查找：在 [1, n] 中寻找满足 check() 的最小 y。 6. 实例验证 样例输入：5 1 和 1 0 1 0 河宽 n=5，x=1，石头高度 [1,0,1,0]（位置 1 和 3 有石头）。计算过程： total_needed = 2x = 2y=4 时：检查区间 [1,4]（石头位置 1 到 4），和 = 1+0+1+0=2 ≥ 2，通过。y=3 时：区间 [1,3] 和=1+0+1=2 ≥ 2，但区间 [2,4] 和=0+1+0=1 < 2，不通过。 输出：4（符合样例）。 7. 测试点与优化建议 关键测试点： 边界情况： n=1：直接跳到终点，输出 1。n=2, x=1, arr=[0]：需 y=2（直接跳过石头）。x=0：输出 0 或 1（根据问题定义）。 性能极限： n=1e5, x=1e9, H_i=1e4：前缀和最大 109，使用 long long。 特殊石头分布： 所有石头高度为 0：需 y >= n。石头集中在两端：如 n=1000, x=500, H[0]=1000, H[999]=1000，验证区间和。 优化建议： 时间复杂度：O(nlogn)（二分 O(logn)，检查 O(n)）。空间优化：前缀和数组可覆盖存储，但 O(n) 已最优。提前终止：检查函数中，任一区间不满足即返回，避免冗余计算。 8. 注意事项 数据范围： 石头高度和可能达 109，使用 long long。输入石头位置从 1 到 n-1，起点 0 和终点 n 无石头。 二分边界： 循环条件 left <= right，更新时 right = mid - 1 或 left = mid + 1。 前缀和索引： prefix[i] 对应 arr[0] 到 arr[i-1] 的和，区间 [i, j] 和为 prefix[j+1]-prefix[i]。 此实现通过二分和前缀和高效解决大规模数据，满足蓝桥杯评测要求。
