贪心算法过河问题 pojo1700

过桥问题：

黑夜，只有一只手电筒
A过桥需要1s
B过桥需要3s
C过桥需要5s
D过桥需要8s
E过桥需要12s
求最小过桥时间

贪心算法：

从最大的开始过去，最小的两个做为辅助。

假如左岸人数为2：两个人直接过去，不需要回来，代价 $T=A_i+A_j (j=i+1)$
假如左岸人数为3：由 $A_i$ 辅助，代价 $T=A_i+A_{i+1}+A_{i+2}$

假如左岸人数大于3：将左岸最大两个人送到右岸，可以有两种方案：

image.png

综上，此时

$T= \begin{cases} A_i+A_j & \text{j-i<2} \\ A_i+A_{i+1}+A_{i+2} & \text{j-i<3}\\ max(2A_i+A_{j-1}+A_j,A_i+2A_{i+1}+A_j) & \text{other}\\ \end{cases}$

tips: 记得每次j-2。

代码如下：

package my;

import java.util.Arrays;
import java.util.Scanner;

public class Poj1700渡河 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++) {
            int n = sc.nextInt();
            int[]speed=new int[n];
            for(int j=0;j<n;j++) {
                speed[j]=sc.nextInt();
            }
            Arrays.sort(speed);
            
            int ans=f(n,speed);
            System.out.println(ans);
        }
    }
    public static int f(int n,int[]speed) {
        int left=n;
        int ans=0;
        while(left>0) {
            if(left==1) {
                ans+=speed[0];
                break;
            }else if(left==2) {
                ans+=speed[1];
                break;
            }else if(left==3) {//有三人
                ans+=speed[2]+speed[0]+speed[1];
                break;
            }else {
                //1,2出发,1返回,        最后两名出发,2返回
                int s1=speed[1]*2+speed[0]+speed[left-1];
                
                //1,3出发,1返回,        1,4出发,1返回         1,2过河
                int s2=speed[left-1]+speed[left-2]+2*speed[0];
                ans+=min(s1,s2);
                left-=2;        //左侧是渡河的起点,left代表还剩渡河的人数
            }
        }
        return ans;
        
    }
    public static int min(int a1,int a2) {
        return a1<=a2?a1:a2;
    }
}

图片解析：