用Java实现:N个人过河,船每次只能坐两个人,船载每个人过河的所需时间不同t[i],每次过河的时间为船上的人的较慢的那个,求最快的过河时间。(船划过去要有一个人划回来)。 假设有7个人要过河,每个人的过河所需要要的时间分别是1,3,4,6,8,2,9 给出解题思路和算法分析
时间: 2024-05-22 16:15:46 浏览: 18
解题思路:
1. 首先将人按照过河所需时间从小到大排序;
2. 每次选择两个过河时间最短的人A和B一起过河,设A的过河时间为a,B的过河时间为b,则本次过河的时间为max(a,b);
3. 将A和B从原来的人群中删除,并将本次过河时间加入总时间中;
4. 如果还有人没有过河,则从剩余的人中选择两个过河时间最短的人继续过河,重复步骤2-3,直到所有人都过河。
算法分析:
时间复杂度:排序的时间复杂度为O(nlogn),每次过河需要选择两个人,因此需要进行n/2次操作,每次操作的时间复杂度为O(1),因此总时间复杂度为O(nlogn+n/2)=O(nlogn)。
空间复杂度:需要一个数组来存储每个人过河所需时间,因此空间复杂度为O(n)。
Java代码实现如下:
import java.util.Arrays;
public class CrossRiver {
public static int getFastestTime(int[] t) {
Arrays.sort(t); // 将人按照过河所需时间从小到大排序
int n = t.length;
int totalTime = 0;
while (n > 3) { // 还有三个以上人没有过河
int t1 = t[0]; // 选择过河时间最短的两个人
int t2 = t[1];
int t3 = t[n-2];
int t4 = t[n-1];
int time1 = t2; // 计算本次过河时间
int time2 = t4;
if (2*t1+t3 < t1+2*t2) {
time1 = 2*t1+t3;
}
if (2*t2+t4 < t1+t3*2) {
time2 = 2*t2+t4;
}
totalTime += Math.min(time1, time2); // 将本次过河时间加入总时间中
if (time1 < time2) { // A和B一起过河
t[1] = t3;
t[2] = time1;
for (int i = 3; i < n-2; i++) {
t[i] = t[i+1];
}
} else { // C和D一起过河
t[0] = t1;
t[1] = time2;
for (int i = n-2; i > 2; i--) {
t[i] = t[i-1];
}
}
n -= 2; // 删除已经过河的两个人
}
if (n == 3) { // 最后三个人过河
totalTime += t[0]+t[1]+t[2];
} else { // 最后两个人过河
totalTime += t[1];
}
return totalTime; // 返回最快的过河时间
}
public static void main(String[] args) {
int[] t = {1,3,4,6,8,2,9};
System.out.println(getFastestTime(t)); // 输出结果为:29
}
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)