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：
步骤描述如下：
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]int
var dp [MAXN]int
var 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;
}