最短路径 求最小值


题:
有1个人,要把n匹马从A村运往B村。
初始时,人和马都在A村。每次骑1匹马牵1匹马,回来时骑1匹马。
已知每匹马从A村到B村需要的时间(数字越大越慢)
两匹马同行时只能迁就较慢者。
求所有马匹都运到B村的最小的运输时间(此时,人和马都在B村)。
程序首先输入一个整数n(n<100),表示有n匹马。
接着是n行整数,表示马从A村到B村的所用的分钟数(小于1000)
程序输出:1个整数,表示所有马匹均运到B村的最小总耗时。
例如,
输入:
3
1
2
4
程序应输出:
7

输入:
4
1
4
2
5
程序应该输出:
12

源码Strategy.java


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

public class Strategy {
    public static void speed(int[] k) {
        Arrays.sort(k);
    //  for (int i=0; i<k.length; i++) {
    //      System.out.println(k[i]);
    //  }
        int t = k.length;
        int a = 0;
        while(true) {
            if (t==0) {
                break;
            }
            else if (t==1) {
                a += k[0];
                break;
            }
            else if (t==2) {
                a += k[1];
                break;
            }
            else if (t==3) {
                a += k[0] + k[1] + k[2];
                break;
            }
            else if (t==4) {
                a += (2*k[1]-k[0]-k[2]>0)? 
                        2*k[0]+k[1]+k[2]+k[3]: k[0]+3*k[1]+k[3];
                break;
            }
            else {
                a += (2*k[1]-k[t-2]-k[0]>0)? 
                        2*k[0]+k[t-2]+k[t-1]: k[0]+2*k[1]+k[t-1];
                t -= 2;
            }
        }
        System.out.println(a);
    }
    
    public static void main(String[] args) {
    /*  try {
            FileInputStream fis= new FileInputStream("/Users/Tro/Desktop/Trial.txt");
            System.setIn(fis);
        }
        catch(IOException e) {
            e.printStackTrace();
        }
    */
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int[] k = new int[s];
        for (int i=0; i<s; i++) {
            k[i] = sc.nextInt();
        }
        sc.close();
        
        speed(k);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注