2023-12-23：用 go 语言，一支 n 个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河
敌军在 T 的时长后到达河面，没到过对岸的士兵都会被消灭
现在军队只找到了 1 只小船，这船最多能同时坐上 2 个士兵。
当 1 个士兵划船过河，用时为 a[i]
当 2 个士兵坐船同时划船过河时, 用时为 max(a[j],a[i])两士兵中用时最长的
当 2 个士兵坐船只有 1 个士兵划船时, 用时为 a[i] * 10, a[i]为划船士兵用时
请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短
我们先看一下如下的题，再讲一下华为 OD 的扩展
来自洛谷的 P1809，过河问题。
有一个大晴天, Oliver 与同学们一共 N 人出游, 他们走到一条河的东岸边，想要过河到西岸
而东岸边有一条小船。船太小了，一次只能乘坐两人，每个人都有一个渡河时间 T
船划到对岸的时间等于船上渡河时间较长的人所用时间
现在已知 N 个人的渡河时间 Ti
Oliver 想要你告诉他，他们最少要花费多少时间，才能使所有人都过河
注意，只有船在东岸（西岸）的人才能坐上船划到对岸。
来自华为 OD。
答案 2023-12-23：
来自左程云。
灵捷3.5
步骤描述如下：
1.初始化输入数据：定义一个整型切片 inputs，包含每个士兵的过河时间。初始化 n 为 inputs 的长度。
2.对士兵的过河时间进行排序：使用 sort 包对 inputs 进行排序，以便后续计算最小花费时间。
3.初始化动态规划数组 dp：定义一个大小为 max(n, 3)的整型数组 dp，用于存储每个状态下的最小花费时间。若 n 大于等于 3，则初始化前三个元素 dp[0]、dp[1]、dp[2]为对应士兵过河时间的和。
4.动态规划求解最小花费时间：从第 3 个士兵开始遍历到第 n 个士兵，对于每个士兵 i，计算以下两种情况的最小值，并更新 dp[i]：
a) 两个士兵同时过河：dp[i-2] + inputs[1] + inputs[0] + inputs[i] + inputs[1]
b) 一个士兵过河：dp[i-1] + inputs[i] + inputs[0]
5.返回最小花费时间：返回 dp[n-1]作为最终的答案，即所有士兵都过河且花费时间最小的方案。
总的时间复杂度：排序士兵过河时间的时间复杂度为 O(nlogn)，动态规划遍历的时间复杂度为 O(n)，因此总的时间复杂度为 O(nlogn)。
总的额外空间复杂度：除了输入外，使用了一个大小为 MAXN 的整型数组 arr 和 dp，因此额外空间复杂度为 O(MAXN)。
go 完整代码如下：
package main
import ( "fmt" "sort")
const MAXN = 100001
var arr [MAXN]intvar dp [MAXN]intvar n int
func main() { inputs := []int{4, 6, 7, 10, 15} ii := 0 n = inputs[ii] ii++ for i := 0; i < n; i++ { arr[i] = inputs[ii] ii++ } ans := minCost() fmt.Println(ans)
}
func minCost() int { sort.Ints(arr[:n]) if n >= 1 { dp[0] = arr[0] } if n >= 2 { dp[1] = arr[1] } if n >= 3 { dp[2] = arr[0] + arr[1] + arr[2] } for i := 3; i < n; i++ { dp[i] = min( dp[i-2]+arr[1]+arr[0]+arr[i]+arr[1], dp[i-1]+arr[i]+arr[0], ) } return dp[n-1]}
func min(a, b int) int { if a < b { return a } return b}
复制代码
rust 完整代码如下：
use std::cmp;
const MAXN: usize = 100001;
static mut ARR: [i32; MAXN] = [0; MAXN];static mut DP: [i32; MAXN] = [0; MAXN];static mut N: usize = 0;
fn main() { let inputs: Vec<i32> = vec![4, 6, 7, 10, 15];
unsafe { let mut ii: usize = 0; N = inputs[ii] as usize; ii += 1;
for i in 0..N { ARR[i] = inputs[ii]; ii += 1; }
let ans = min_cost(); println!("{}", ans); }}
unsafe fn min_cost() -> i32 { ARR[0..N].sort();
if N >= 1 { DP[0] = ARR[0]; } if N >= 2 { DP[1] = ARR[1]; } if N >= 3 { DP[2] = ARR[0] + ARR[1] + ARR[2]; }
for i in (3..N).step_by(1) { DP[i] = cmp::min( DP[i - 2] + ARR[1] + ARR[0] + ARR[i] + ARR[1], DP[i - 1] + ARR[i] + ARR[0], ); }
return DP[N - 1];}
复制代码
c++完整代码如下：
#include <iostream>#include <algorithm>
const int MAXN = 100001;
int arr[MAXN];int dp[MAXN];int n;
int minCost() { std::sort(arr, arr + n);
if (n >= 1) { dp[0] = arr[0]; } if (n >= 2) { dp[1] = arr[1]; } if (n >= 3) { dp[2] = arr[0] + arr[1] + arr[2]; }
for (int i = 3; i < n; i++) { dp[i] = std::min( dp[i - 2] + arr[1] + arr[0] + arr[i] + arr[1], dp[i - 1] + arr[i] + arr[0] ); }
return dp[n - 1];}
int main() { int inputs[] = { 4, 6, 7, 10, 15 };
int ii = 0; n = inputs[ii++];
for (int i = 0; i < n; i++) { arr[i] = inputs[ii++]; }
int ans = minCost();
std::cout << ans << std::endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
#define MAXN 100001
int arr[MAXN];int dp[MAXN];int n;
int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b);}
int minCost() { qsort(arr, n, sizeof(int), compare);
if (n >= 1) { dp[0] = arr[0]; } if (n >= 2) { dp[1] = arr[1]; } if (n >= 3) { dp[2] = arr[0] + arr[1] + arr[2]; }
for (int i = 3; i < n; i++) { dp[i] = min( dp[i - 2] + arr[1] + arr[0] + arr[i] + arr[1], dp[i - 1] + arr[i] + arr[0] ); }
return dp[n - 1];}
int main() { int inputs[] = { 4, 6, 7, 10, 15 };
int ii = 0; n = inputs[ii++];
for (int i = 0; i < n; i++) { arr[i] = inputs[ii++]; }
int ans = minCost(); printf("%d\n", ans);
return 0;}
复制代码
评论