2023-12-23：用go语言，一支n个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河

敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭

现在军队只找到了1只小船，这船最多能同时坐上2个士兵。

1. 当1个士兵划船过河，用时为a[i]

2. 当2个士兵坐船同时划船过河时, 用时为max(a[j],a[i])两士兵中用时最长的

3. 当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]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;
}