2024-01-06：用go语言，在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧

在桥上有一些石子，青蛙很讨厌踩在这些石子上

由于桥的长度和青蛙一次跳过的距离都是正整数

我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0...L

其中L是桥的长度，坐标为 0 的点表示桥的起点，坐标为 L 的点表示桥的终点

青蛙从桥的起点开始，不停的向终点方向跳跃

一次跳跃的距离是 S 到 T 之间的任意正整数（包括S,T）

当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度 L，青蛙跳跃的距离范围[S,T]，

以及桥上石子的位置。

你的任务是确定青蛙要想过河，最少需要踩到的石子数。

来自华为社招笔试。

答案2024-01-06：

来自左程云。

灵捷3.5

大体步骤如下：

1.读入桥的长度 L、跳跃的最小距离 S、最大距离 T 和石子的位置数组。

2.如果起点和终点相同，即 S 等于 T，则遍历石子数组，计算能够整除 S 的石子数量，并输出结果。

3.否则，将石子位置数组排序，并计算可以减少的最小跳跃距离 cut，该值等于 S 和 T 之间的最小值。

4.初始化距离数组 distance，并将最小距离初始值设为 0。同时设置一个 stone 数组，记录可能存在石子的位置。

5.遍历石子位置数组，计算每个石子之间的距离，并将距离标记在 distance 数组中，同时在 stone 数组中将对应位置设为 true。

6.更新桥的长度为 distance 数组中的最后一个数和 cut 的较小值。

7.初始化 dp 数组，长度为桥的长度加一，并将每个位置的初始值设为 MAXN。

8.动态规划求解 dp 数组，计算最少需要踩到的石子数。

• 对于每个位置 i，从 i-s 到 i-t 之间的位置 j，取 dp[j] 的最小值，再加上是否有石子的判断 boolToInt(stone[i])。

9.遍历 distance 数组的最后一个数加一到桥的长度 l，取 dp 数组中的最小值，即为最少需要踩到的石子数。

10.输出结果。

总的时间复杂度是 O(m log m + l * t)，其中 m 是石子数量，l 是桥的长度，t 是最大跳跃距离；

总的额外空间复杂度是 O(l + t)。

go完整代码如下：

package main

import (
	"fmt"
	"sort"
)

const (
	MAXN = 101
	MAXL = 100001
	MAXK = 201
)

var (
	arr             [MAXN]int
	distance        [MAXN]int
	dp              [MAXL]int
	stone           [MAXL]bool
	reach           [MAXK]bool
	l, s, t, m, cut int
)

func main() {
	inputs := []int{10,
		2, 3, 5,
		2, 3, 5, 6, 7}
	ii := 0
	l = inputs[ii]
	ii++
	s = inputs[ii]
	ii++
	t = inputs[ii]
	ii++
	m = inputs[ii]
	ii++

	for i := 1; i <= m; i++ {
		arr[i] = inputs[ii]
		ii++
	}
	if s == t {
		ans := 0
		for i := 1; i <= min(l, m); i++ {
			if arr[i]%s == 0 {
				ans++
			}
		}
		fmt.Println(ans)
	} else {
		sort.Ints(arr[1 : m+1])
		cut = reduce(s, t)
		for i := 1; i <= m; i++ {
			distance[i] = distance[i-1] + min(arr[i]-arr[i-1], cut)
			stone[distance[i]] = true
		}
		l = min(l, distance[m]+cut)
		for i := 1; i <= l; i++ {
			dp[i] = MAXN
		}
		for i := 1; i <= l; i++ {
			for j := max(i-t, 0); j <= i-s; j++ {
				dp[i] = min(dp[i], dp[j]+boolToInt(stone[i]))
			}
		}
		ans := MAXN
		for i := distance[m] + 1; i <= l; i++ {
			ans = min(ans, dp[i])
		}
		fmt.Println(ans)
	}
}

func reduce(s int, t int) int {
	for i := range reach {
		reach[i] = false
	}
	cnt := 0
	ans := 0
	for i := 0; i < MAXK; i++ {
		for j := i + s; j < min(i+t+1, MAXK); j++ {
			reach[j] = true
		}
		if !reach[i] {
			cnt = 0
		} else {
			cnt++
		}
		if cnt == t {
			ans = i
			break
		}
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func boolToInt(b bool) int {
	if b {
		return 1
	}
	return 0
}

c++完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 101;
const int MAXL = 100001;
const int MAXK = 201;

int arr[MAXN];
int distance0[MAXN];
int dp[MAXL];
bool stone[MAXL];
bool reach[MAXK];

int l, s, t, m, cut;

int reduce(int s, int t) {
    fill(reach, reach + MAXK, false);
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < MAXK; i++) {
        for (int j = i + s; j < min(i + t + 1, MAXK); j++) {
            reach[j] = true;
        }
        if (!reach[i]) {
            cnt = 0;
        }
        else {
            cnt++;
        }
        if (cnt == t) {
            ans = i;
            break;
        }
    }
    return ans;
}

int main() {
    int inputs[] = { 10, 2, 3, 5, 2, 3, 5, 6, 7 };
    int ii = 0;
    l = inputs[ii++];
    s = inputs[ii++];
    t = inputs[ii++];
    m = inputs[ii++];

    for (int i = 1; i <= m; i++) {
        arr[i] = inputs[ii++];
    }
    if (s == t) {
        int ans = 0;
        for (int i = 1; i <= min(l, m); i++) {
            if (arr[i] % s == 0) {
                ans++;
            }
        }
        cout << ans << endl;
    }
    else {
        sort(arr + 1, arr + m + 1);
        cut = reduce(s, t);
        for (int i = 1; i <= m; i++) {
            distance0[i] = distance0[i - 1] + min(arr[i] - arr[i - 1], cut);
            stone[distance0[i]] = true;
        }
        l = min(l, distance0[m] + cut);
        for (int i = 1; i <= l; i++) {
            dp[i] = MAXN;
        }
        for (int i = 1; i <= l; i++) {
            for (int j = max(i - t, 0); j <= i - s; j++) {
                dp[i] = min(dp[i], dp[j] + (stone[i] ? 1 : 0));
            }
        }
        int ans = MAXN;
        for (int i = distance0[m] + 1; i <= l; i++) {
            ans = min(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

c语言代码如下：

#include <stdio.h>
#include <stdbool.h>

#define MAXN 101
#define MAXL 100001
#define MAXK 201

int arr[MAXN];
int distance[MAXN];
int dp[MAXL];
bool stone[MAXL];
bool reach[MAXK];
int l, s, t, m, cut;

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int reduce(int s, int t) {
    for (int i = 0; i < MAXK; i++) {
        reach[i] = false;
    }
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < MAXK; i++) {
        for (int j = i + s; j < (i + t + 1 < MAXK ? i + t + 1 : MAXK); j++) {
            reach[j] = true;
        }
        if (!reach[i]) {
            cnt = 0;
        }
        else {
            cnt++;
        }
        if (cnt == t) {
            ans = i;
            break;
        }
    }
    return ans;
}

void sortInts(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printAns(int ans) {
    printf("%d\n", ans);
}

int main() {
    int inputs[] = { 10, 2, 3, 5, 2, 3, 5, 6, 7 };
    int ii = 0;
    l = inputs[ii++];
    s = inputs[ii++];
    t = inputs[ii++];
    m = inputs[ii++];

    for (int i = 1; i <= m; i++) {
        arr[i] = inputs[ii++];
    }
    if (s == t) {
        int ans = 0;
        for (int i = 1; i <= min(l, m); i++) {
            if (arr[i] % s == 0) {
                ans++;
            }
        }
        printAns(ans);
    }
    else {
        sortInts(arr + 1, m);
        cut = reduce(s, t);
        for (int i = 1; i <= m; i++) {
            distance[i] = distance[i - 1] + min(arr[i] - arr[i - 1], cut);
            stone[distance[i]] = true;
        }
        l = min(l, distance[m] + cut);
        for (int i = 1; i <= l; i++) {
            dp[i] = MAXN;
        }
        for (int i = 1; i <= l; i++) {
            for (int j = max(i - t, 0); j <= i - s; j++) {
                dp[i] = min(dp[i], dp[j] + (stone[i] ? 1 : 0));
            }
        }
        int ans = MAXN;
        for (int i = distance[m] + 1; i <= l; i++) {
            ans = min(ans, dp[i]);
        }
        printAns(ans);
    }
    return 0;
}

本栏目推荐文章
• 一行代码解决Three.js中只能在一侧看到物体的问题
• 2024-01-06：用go语言，在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子，青蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥
• AcWing 282. 石子合并
• NEFU OJ Problem 1489 青蛙赶路 题解【动态规划DP】
• 「题解」P6791 [SNOI2020] 取石子
• P1880 [NOI1995] 石子合并
• 四个代码融合 依次：小青蛙上台阶 ；求阶乘；求最大公因数；地盘划分(均为递归算法)
• 【UR #26】石子合并
• 关于独木桥问题中的一些经验总结
• 青蛙跳台阶（C语言数学排列组合公式求解法）

独木桥 独木 青蛙 一侧 石子独木桥 独木 青蛙 一侧 独木桥 独木 独木桥 独木 独木桥 独木p1007 独木桥 独木luogu p1007 独木舟 独木桥 独木 经验 问题 独木舟 独木 一侧