首页 > 试题广场 >

过河

[编程题]过河

热度指数：3752 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

数据范围： $1\le L \le 10^9 \$ ， $1 \le S \le T \le 10 \$ ， $1\le M \le 100 \$

输入描述:

第一行有一个正整数L ，表示独木桥的长度。
第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数
第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。
所有相邻的整数之间用一个空格隔开。

输出描述:

只包括一个整数，表示青蛙过河最少需要踩到的石子数。

示例1

输入

10
2 3 5
2 3 5 6 7

输出

算法知识视频讲解

牛客278895174号

可以踩水跳嘛，题目没说清楚啊

发表于 2022-04-23 22:26:58 回复(1)

Python 3

牛客鲁1号

超时超到心憔悴

发表于 2025-03-20 14:51:19 回复(0)

Python3

牛客351477353号

L = int(input())
S,T,M = map(int,input().split())
Location=list(map(int,input().split()))

count =0
if M==0:
    print(0)
for i in range(0,M):
    if Location[i]==S&nbs***bsp;Location[i]==T and L -Location[i]>=0:
        count +=1
    else:
        break
print(count)

发表于 2025-05-19 15:31:25 回复(0)

Python3

南肯辛顿男子技校冯师傅

def solve():

import sys

input_data = sys.stdin.read().strip().split()

if not input_data:

return

it = iter(input_data)

L = int(next(it))

S = int(next(it))

T = int(next(it))

M = int(next(it))

stones = [int(next(it)) for _ in range(M)]

# 特判：如果 S == T，则青蛙每次只能跳固定距离，只有正好落在石子位置才会踩到石子

if S == T:

ans = 0

for stone in stones:

# 从 0 开始，每隔 S 跳一次，正好落在石子上的即踩到了石子

if stone % S == 0:

ans += 1

print(ans)

return

# S < T 的情况：

# 为了避免在[0, L]上开一个超大数组，我们对重要的位置进行“坐标压缩”

# 将起点、石子、终点构成的原始坐标 positions 排序，

# 然后用 d[i] 表示从起点到 positions[i] 的“有效距离”，其中相邻距离如果大于 T，则只记 T

stones.sort()

positions = [0] + stones + [L]

npos = len(positions)

d = [0] * npos

for i in range(1, npos):

gap = positions[i] - positions[i - 1]

if gap > T:

gap = T

d[i] = d[i - 1] + gap

# d[-1] 即为终点 L 对应的压缩坐标

max_coord = d[-1]

# 为了最后一步跳跃可能跳出终点，我们建立 dp 数组大小为 max_coord + T + 1

dp_size = max_coord + T + 1

INF = float('inf')

dp = [INF] * (dp_size)

dp[0] = 0

# 用 stoneMark 数组标记哪些压缩坐标上有石子（注意：起点和终点没有石子）

stoneMark = [0] * (dp_size)

# positions[1:-1] 对应的都是石子的位置

for i in range(1, npos - 1):

stoneMark[d[i]] = 1

# 状态转移：

# dp[i] 表示“压缩坐标”为 i 时，达到该位置最少踩到的石子数

# 青蛙可以从 [i-T, i-S] 跳到 i（注意边界控制）

for i in range(1, dp_size):

jstart = max(0, i - T)

jend = i - S

if jend < jstart:

continue

best = INF

for j in range(jstart, jend + 1):

if dp[j] < best:

best = dp[j]

if best == INF:

continue

# 当 i <= max_coord 时，i 位置对应的是原坐标上的位置，

# 如果该位置有石子（stoneMark[i]==1），则必须加 1；而当 i > max_coord，

# 意味着青蛙已经跳出压缩区间（也即原问题中的 L 之后），无需加石子代价。

if i <= max_coord:

dp[i] = best + stoneMark[i]

else:

dp[i] = best

# 最后答案为在[ max_coord, max_coord+T ]范围内 dp 的最小值

ans = INF

for i in range(max_coord, max_coord + T + 1):

if dp[i] < ans:

ans = dp[i]

print(ans)

if __name__ == '__main__':

solve()

发表于 2025-04-05 22:25:17 回复(0)

lialu1

用例输入：

44278

9 9 20

2357 2624 6266 7004 8710 10741 16235 17405 18823 24254 25750 30959 31376 31593 33729 35216 39090 40122 41299 44184

预期输出：

为啥是1啊，哪个石头被踩到了？都不能被9整除啊？

发表于 2023-05-04 22:53:36 回复(1)

牛客838085381号

为什么输出是2，而不是3

发表于 2022-06-26 11:08:11 回复(2)

Java

ByteWong.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;



// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int s = in.nextInt();
            int t = in.nextInt();
            int m = in.nextInt();
            ArrayList<Integer> stones = new ArrayList();
            for(int i=0;i<m;i++) {
                stones.add(in.nextInt());
            }
            Collections.sort(stones);

            if(s==t) {
                singleJudge(s,stones);
            } else {
                rangeJudge(s,t,n,stones);
            }
        }
    }

    public static void singleJudge(int s,ArrayList<Integer> stones) {
        int stoneNumber = 0;
        for(int i=0;i<stones.size();i++) {
            if(stones.get(i)%s == 0) {
                stoneNumber++;
            }
        }
        System.out.println(stoneNumber);
    }

    public static void rangeJudge(int s,int t,int n,ArrayList<Integer> stones) {
        int compressLen = compressBridgeLength(stones,n,t);
        int[] dp = new int[compressLen+t+1];
        Arrays.fill(dp,10000);
        dp[0] = 0;
        int stoneNumber = 10000;
        int maxStep = 0;
        for(int i=s;i<=compressLen+t;i++) {
            maxStep = Math.max(maxStep,i);
            for(int j=s;j<=t;j++) {
                if(i>=j) {
                    dp[i] = Math.min(dp[i],dp[i-j]);
                }
            }
            if(stones.contains(i)) {
                dp[i] +=1;
            }
        }
        
        for(int i=compressLen;i<=maxStep;i++) {
            stoneNumber = Math.min(dp[i],stoneNumber);
        }
        System.out.println(stoneNumber);
    }

    public static int compressBridgeLength(ArrayList<Integer> stones,int n,int t) {
        for(int i=1;i<stones.size();i++) {
            int distance = stones.get(i) - stones.get(i-1);
            stones.set(i,stones.get(i-1) + distance%90);
        }
        n = (n - stones.get(stones.size()-1))%90 + stones.get(stones.size()-1);
        return n; 
    }
}

发表于 2022-05-05 13:50:13 回复(0)