2023-08-06：小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar
2023-08-06：小青蛙住在一條河邊, 它想到河對(duì)岸的學(xué)校去學(xué)習(xí)
小青蛙打算經(jīng)過河里 的石頭跳到對(duì)岸
河里的石頭排成了一條直線, 小青蛙每次跳躍必須落在一塊石頭或者岸上
給定一個(gè)長(zhǎng)度為n的數(shù)組arr，表示每塊兒石頭的高度數(shù)值
每塊石頭有一個(gè)高度, 每次小青蛙從一塊石頭起跳
這塊石頭的高度就會(huì)下降1, 當(dāng)石頭的高度下降到0時(shí)
小青蛙不能再跳到這塊石頭上(跳躍后使石頭高度下降到0是允許的)
小青蛙一共需要去學(xué)校上x天課, 所以它需要往返x次(去x次，回x次)
當(dāng)小青蛙具有 一個(gè)跳躍能力y時(shí), 它能跳不超過y的距離。
請(qǐng)問小青蛙的跳躍能力至少是多少才能用這些石頭上完x次課？
1 <= n <= 10^5，
1 <= arr[i] <= 10^4，
1 <= x <= 10^9。
來(lái)自藍(lán)橋杯練習(xí)題。
來(lái)自左神
答案2023-08-06：
大體步驟如下：
1.讀取輸入：從輸入中讀取每塊石頭的高度數(shù)值和小青蛙需要上課的天數(shù)x。
2.初始化變量和數(shù)組：定義一個(gè)長(zhǎng)度為n的數(shù)組help用于保存每塊石頭的高度數(shù)值的累積和。初始化變量ans為0。
3.計(jì)算累積和：遍歷數(shù)組arr中的每個(gè)元素，計(jì)算它們的累積和，并保存到數(shù)組help中。
4.計(jì)算最小跳躍能力：使用雙指針法逐個(gè)計(jì)算每個(gè)起點(diǎn)石頭l到終點(diǎn)石頭r的跳躍能力。在每次迭代中，通過移動(dòng)r指針使得help[r] - help[l-1] >= 2*x，即小青蛙能從起點(diǎn)石頭跳躍到終點(diǎn)石頭。同時(shí)，更新ans為當(dāng)前最大的能連續(xù)跳躍的石頭數(shù)量。
5.返回結(jié)果：返回ans作為小青蛙的最小跳躍能力。
總的時(shí)間復(fù)雜度為O(n)，總的空間復(fù)雜度為O(n)。
go完整代碼如下：
package main
import (
"fmt"
)
const MAXN = 100001
var help [MAXN]int
var n, x int
var 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)的最優(yōu)解
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)的最優(yōu)解
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;
}
總結(jié)
以上是生活随笔為你收集整理的2023-08-06：小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： WPF性能优化：Freezable 对象
- 下一篇： Java基础知识1-10