2023-08-06：小青蛙住在一条河边, 它想到河对岸的学校去学习
小青蛙打算经过河里 的石头跳到对岸
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上
给定一个长度为 n 的数组 arr，表示每块儿石头的高度数值
每块石头有一个高度, 每次小青蛙从一块石头起跳
这块石头的高度就会下降 1, 当石头的高度下降到 0 时
小青蛙不能再跳到这块石头上(跳跃后使石头高度下降到 0 是允许的)
小青蛙一共需要去学校上 x 天课, 所以它需要往返 x 次(去 x 次，回 x 次)
当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课？
1 <= n <= 10^5，
1 <= arr[i] <= 10^4，
1 <= x <= 10^9。
来自蓝桥杯练习题。
来自左神
答案 2023-08-06：
#大体步骤如下：
1.读取输入：从输入中读取每块石头的高度数值和小青蛙需要上课的天数 x。
2.初始化变量和数组：定义一个长度为 n 的数组 help 用于保存每块石头的高度数值的累积和。初始化变量 ans 为 0。
3.计算累积和：遍历数组 arr 中的每个元素，计算它们的累积和，并保存到数组 help 中。
4.计算最小跳跃能力：使用双指针法逐个计算每个起点石头 l 到终点石头 r 的跳跃能力。在每次迭代中，通过移动 r 指针使得 help[r] - help[l-1] >= 2*x，即小青蛙能从起点石头跳跃到终点石头。同时，更新 ans 为当前最大的能连续跳跃的石头数量。
5.返回结果：返回 ans 作为小青蛙的最小跳跃能力。
总的时间复杂度为 O(n)，总的空间复杂度为 O(n)。
go 完整代码如下：
package main
import ( "fmt")
const MAXN = 100001
var help [MAXN]intvar n, x intvar sc = []int{5, 1, 1, 0, 1, 0}var ii = 0
func next() int { ii++ return sc[ii-1]}
func hasNext() bool { return ii < len(sc)}
func main() { for hasNext() { n = next() x = next()
for i := 1; i < n; i++ { val := next() help[i] = help[i-1] + val } fmt.Println(minAbility()) }}
// O(N)的最优解func minAbility() int { ans := 0 for l, r := 1, 1; l < n; l++ { for r < n && help[r]-help[l-1] < 2*x { r++ } ans = max(ans, r-l+1) } return ans}
func max(a, b int) int { if a > b { return a } return b}
复制代码
rust 完整代码如下：
const MAXN: usize = 100001;
static mut HELP: [i64; MAXN] = [0; MAXN];static mut N: i64 = 0;static mut X: i64 = 0;static mut SC: [i64; 6] = [5, 1, 1, 0, 1, 0];static mut II: usize = 0;
fn next() -> i64 { unsafe { II += 1; SC[II - 1] }}
fn has_next() -> bool { unsafe { II < SC.len() }}
fn main() { unsafe { while has_next() { N = next(); X = next();
for i in 1..N { let val = next(); HELP[i as usize] = HELP[i as usize - 1] + val; } println!("{}", min_ability()); } }}
// O(N)的最优解fn min_ability() -> i64 { let mut ans: i64 = 0; unsafe { let mut l: i64 = 1; let mut r: i64 = 1; while l < N { while r < N && HELP[r as usize] - HELP[(l - 1) as usize] < 2 * X { r += 1; } ans = max(ans, r - l + 1); l += 1; } } ans}
fn max(a: i64, b: i64) -> i64 { if a > b { a } else { b }}
复制代码
c++完整代码如下：
#include <stdio.h>
#define MAXN 100001
int help[MAXN];int n, x;int sc[] = { 5, 1, 1, 0, 1, 0 };int ii = 0;
int next() { ii++; return sc[ii - 1];}
int hasNext() { return ii < sizeof(sc) / sizeof(sc[0]);}
int min(int a, int b) { return (a < b) ? a : b;}
int max(int a, int b) { return (a > b) ? a : b;}
int minAbility() { int ans = 0; for (int l = 1, r = 1; l < n; l++) { while (r < n && help[r] - help[l - 1] < 2 * x) { r++; } ans = max(ans, r - l + 1); } return ans;}
int main() { while (hasNext()) { n = next(); x = next();
for (int i = 1; i < n; i++) { int val = next(); help[i] = help[i - 1] + val; } printf("%d\n", minAbility()); }
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>
#define MAXN 100001
int help[MAXN];int n, x;int sc[] = { 5, 1, 1, 0, 1, 0 };int ii = 0;
int next() { ii++; return sc[ii - 1];}
int hasNext() { return ii < sizeof(sc) / sizeof(sc[0]);}
int min(int a, int b) { return (a < b) ? a : b;}
int max(int a, int b) { return (a > b) ? a : b;}
int minAbility() { int ans = 0; for (int l = 1, r = 1; l < n; l++) { while (r < n && help[r] - help[l - 1] < 2 * x) { r++; } ans = max(ans, r - l + 1); } return ans;}
int main() { while (hasNext()) { n = next(); x = next();
for (int i = 1; i < n; i++) { int val = next(); help[i] = help[i - 1] + val; } printf("%d\n", minAbility()); }
return 0;}
复制代码
评论