【输入】
【输出】
输出的第一行给出所有n个人过桥的总的秒数，接下来的若干行给出实现策略。每行包括一个或两个整数，表示组成一组过桥的一个或两个人，以所用的时间标识。
总共：17 秒
去：1 2
回：1
去：5 10
回：2
去：1 2
【分析】由于一次过桥最多两人且手电筒需要往返传递，因此以两个成员过桥为一个分析单位，计算过桥时间。以按过桥时间递增的顺序将n个成员排序。则a[1]是最快的人，a[2]次之，a[n]是最慢的人，a[n-1]是倒数第二慢的人。在相对状况下考虑，则有两种方案：
- 用最快的成员a[1]传递手电筒帮助最慢的a[n]和a[n-1]过桥，易知来回所用的时间为2*a[1]+a[n]+a[n-1]
用最快的成员a[1]和次快的成员a[2]传递手电筒帮助最慢的a[n]和a[n-1]过桥，具体方案如下：
1.a[1]和a[2]到对岸，所用时间为a[2];
2.a[1]返回，将手电筒给最慢的a[n]和a[n-1]，并且a[n]和a[n-1]到对岸后将手电筒交给a[2]，所用时间为：a[1]+a[n];
3.a[2]返回,所用时间为a[2];
综合起来方案二所用的总时间为2*a[2]+a[n]+a[1]。显然，两种方案的好坏取决于他们的总时间，若2a[1]+a[n]+a[n-1]<2a[2]+a[n]+a[1]，即采用第一种方案，否则采用第二种方案。我们每次帮助最慢的两个人过桥，累加时间，最后可能出现的两种情况：
1.对岸剩下两个队员，全部过桥，时间为a[2];
2.对岸剩下三个队员，用最快的成员传递手电筒，帮助最慢的成员过桥，然后与次慢的成员一起过桥，时间为：a[1]+a[n-1]+a[n]，注意，这里的n=3。package com.wxw.online; import java.util.Scanner; /**
* @Author: wxw
* @create: 2019-10-17-10:41
*/ public class GreedBridge {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n, i, k;//人数为n,i,j,k为循环控制变量，数组存储过桥时间
int[] a = new int[1024];
int sum = 0; //过桥总时间
n = sc.nextInt();
for (i = 1; i <= n; i++)
a[i] = sc.nextInt();
if (n == 1) {
System.out.format(a[1] + "%n" + a[1]);
}
k = n;
while (k > 3) //求总时间
{
//分情况讨论
if (a[1] + a[k - 1] < 2 * a[2])
sum += a[k] + a[1] * 2 + a[k - 1];
else
sum += a[2] * 2 + a[1] + a[k];
k -= 2;
}
if (k == 2) //对岸剩下两个成员
sum += a[2];
else //对岸剩下3个成员
sum += a[1] + a[2] + a[3];
System.out.println(sum);//输出n个人的过桥时间
k = n;
while (k > 3) //输出具体方案
{
if (a[1] + a[k - 1] < 2 * a[2]) //输出用a[1]传递手电筒方案
{
System.out.format(a[1] + " " + a[k] + "%n" + a[1] + "%n" + a[1] + " " + a[k - 1] + "%n" + a[1]);
} else //输出用a[1]、a[2]传递手电筒发的方案
{
System.out.format(a[1] + " " + a[2] + "%n" + a[1] + "%n" + a[k] + " " + a[k - 1] + "%n" + a[2] + "%n");
k -= 2;
}
if (k == 2)
System.out.println(a[1] + " " + a[2]);
else { System.out.format(a[1] + " " + a[3] + "%n" + a[1] + "%n" + a[1] + " " + a[2]);
} }
}
}