2024-01-06：用go语言，在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧
在桥上有一些石子，青蛙很讨厌踩在这些石子上
由于桥的长度和青蛙一次跳过的距离都是正整数
我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0...L
其中L是桥的长度，坐标为 0 的点表示桥的起点，坐标为 L 的点表示桥的终点
青蛙从桥的起点开始，不停的向终点方向跳跃
一次跳跃的距离是 S 到 T 之间的任意正整数（包括S,T）
当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度 L，青蛙跳跃的距离范围[S,T]，
以及桥上石子的位置。
你的任务是确定青蛙要想过河，最少需要踩到的石子数。
来自华为社招笔试。
答案2024-01-06：
来自左程云。
大体步骤如下：
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;
}