首页 > 其他分享 >2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar

2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar

时间:2023-08-06 18:01:44浏览次数:52  
标签:return help int 青蛙 石头 对岸 ans next

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]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)的最优解
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
}

2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar_#define

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
    }
}

2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar_数组_02

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;
}

2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar_i++_03

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;
}

2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头跳到对岸 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上 给定一个长度为n的数组ar_#define_04

标签:return,help,int,青蛙,石头,对岸,ans,next
From: https://blog.51cto.com/moonfdd/6985803

相关文章

  • 2023-08-06:小青蛙住在一条河边, 它想到河对岸的学校去学习 小青蛙打算经过河里 的石头
    2023-08-06:小青蛙住在一条河边,它想到河对岸的学校去学习小青蛙打算经过河里的石头跳到对岸河里的石头排成了一条直线,小青蛙每次跳跃必须落在一块石头或者岸上给定一个长度为n的数组arr,表示每块儿石头的高度数值每块石头有一个高度,每次小青蛙从一块石头起跳这块石头的......
  • 石头剪子布
    #include<iostream>usingnamespacestd;//使用string字符串解决。intmain(){strings1,s2;intn;cin>>n;for(inti=0;i<n;i++){cin>>s1>>s2;if(s1==s2){cout<<"Tie"<<en......
  • 小青蛙跳台阶
    #include<iostream>usingnamespacestd;inta(intn){if(n<=2){returnn;}else{returna(n-1)+a(n-2);}}intmain(intargc,char**argv){system("pause");intN;cin>>N;cout<<......
  • 80km/h 撞到了这么大的石头
    这周一7月17日,飞车80km/h,再加上玻璃脏没贴膜,很远就看到桥下(在水溃桥)那边有异样,地表有黄色不明物质,侥幸没减速,快走到跟前了才发现有几块大石头,来不及刹车了,然后就是跳得很高了,就是那种减震被压缩到底的声音,哐哐哐!下车检查,也没爆胎,也没有漏机油!这破车质量还是可以的,如果是倭系,早就断......
  • 代码随想录算法训练营第三十三天| 1049. 最后一块石头的重量 II 494. 目标和 474.一
    1049.最后一块石头的重量II思路:因为含有两个石头的相撞,所以需要把dp的目标值改成sum/2,然后取得这个目标值的最大值,然后对sum-2*target代码:1//要求:有多个石头,两两撞击,取得剩下的石头的最小值2//——》一定要碰到最后一个3//注意:4//1,x==y:两个粉碎,x<y:y=......
  • php做网页版剪刀石头布的功能
    实例讲述了php实现的网页版剪刀石头布攻略在玩游网上的设计。分享给大家供大家参考,具体如下:<?php/**Createdon2016-11-25**/if(isset($_POST['sub'])){$what=$_POST['what'];//需要输入的数组$my_array=array("剪刀","石头","布");//获胜规则$guize=a......
  • 最后一块石头的重量
    有一堆石头,每块石头的重量都是正整数。每一回合,从中选出两块最重的石头,然后将它们一起粉碎。假设石头的重量分别为 x和 y,且 x<=y。那么粉碎的可能结果如下:如果 x==y,那么两块石头都会被完全粉碎;如果 x!=y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新......
  • J J BOND and超比组合 剪刀石头布
    constintMAX=10; srand(time(0)); intm,n,countm,countn; countm=countn=0; for(inti;i<MAX;i++){ m=rand()%3+1; cout<<"YouareJJBOND,comeon!"<<endl; cout<<"1,2,3,JJBOND"<<endl; cin>>n; if(n<......
  • 判断语句+ random的应用-剪刀石头布游戏
    1'''2需求:31.通过人机交换实现您的出拳(input函数的应用)42.通过伪随机数模块random实现模拟对手出拳53.然后进行数据处理,得出结果64.输入数字非0、1、2退出7'''89importrandom#导入随机数模块random1011whileTrue:12#人机交换:pla......
  • 牛客小白月赛74 G 跳石头,搭tizi
    题目链接)数据范围,2e5区间越长越省力。对于一个起点来说,从这里搭tizi最远到达的是序列中右侧第一个大于它的数所在的位置。用单调栈可以找到这样的区间,这些区间大致如下所示。就是最多只会有包含的情况,但是不会出现交叉的情况。然后可以这样渐次登高,到达最顶端。下降的......