题目
晚上有四个人要过桥,只有一个手电筒,每次过桥都需要手电筒,每次最多可同时过两个人,其中甲过桥要1分钟,乙要2分钟,丙要5分钟,丁要10分钟。求最短的过桥时间。
一、思路
首先从四个人开始分析。
很明显从桥的一边到另一边的时间主要由慢的人确定,但是每次都需要来回运送手电,要想时间更少那么送手电的人速度就必须要快,很明显要么最快的带次慢和最慢的人过去,要么最快和次快的先过去然后让两个慢的一起过去。
甲–A
乙–B
丙–C
丁–D
方法一:
AD过桥----A返回
AC过桥----A返回
AB过桥--------一共用时 10+1+5+1+2=19min
方法二:
AB过桥----A返回
CD过桥----B返回
AB过桥-------一共用时 2+1+10+2+2=17min
甲乙过桥----甲返回
丙丁过桥----乙返回
甲乙过桥-------一共用时2+1+10+2+2=17min
当前发现这个方式是最快的。
并且这两种方式过桥的最后一趟一定是由次快的人的速度决定
所以这两种方式时间可以写成一个通式:
方法一:time=D+A+C+A(+B)=2A+C+D(+B)
方法二:time=B+A+D+B(+B)=2B+A+D(+B)
2A+C+D=2B+A+D---->A+C=2B
把两种方法所用时间进行比较就能得出那种更快了。
所以当A+C>2B的时候方法二要快,反之。
n<4的情况就不用说了。
如果人数为n的话(n>=4)
只需要简单的使用一下递归,每次送两个人过桥就好了。
二、代码
代码如下:
public class text2 {
public static void quick_sort(int arr[], int l, int r){
/*
* 快速排序*/
if(l>=r) return;
int q=arr[(l+r)>>1],i=l-1,j=r+1;//分界点和边界
while(i<j){
do i++; while (q>arr[i]);
do j--; while (q<arr[j]);
if(i<j){
int t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
}
quick_sort(arr, l, j);
quick_sort(arr, j+1, r);
/*for (int i :
arr) {
System.out.println(i);
}*/
}
public static void main (String [] args){
int n=new Scanner(System.in).nextInt();//人数
int arr[]=new int[n];//每人过桥时间
for(int i=0;i<n;i++){
arr[i]=new Scanner(System.in).nextInt();
}
quick_sort(arr,0,n-1);
System.out.print(short_time(arr,n));
}
public static int short_time(int arr[],int n){//传入每人过桥时间和人数
int number=n,time=0;
if (n<4)
switch (n){
case 1: return arr[0];
case 2: return arr[1];
case 3: return arr[0]+arr[1]+arr[2];
}
else {
int a=arr[0],b=arr[1],c=arr[n-2],d=arr[n-1];
// 最快 次快 次慢 最慢
//2*b+a+d || 2*a+c+d
if((2*b+a+d)<(2*a+c+d)){
time=2*b+a+d;
}else {
time=2*a+c+d;
}
number-=2;
}
time+=short_time(arr,number);
return time;
}
}
测试数据
4
1
2
5
10
17