UVA-10037 Bridge---过河问题进阶版（贪心）

题目链接：

题目大意：

N个人夜里过河，总共只有一盏灯，每次最多过两个人，然后需要有人将灯送回

才能继续过人，每个人过桥都需要耗费一定的时间，让你求耗费的最少时间，并输出过河方案

思路：

和之前POJ-1700一样，不过这里要求输出每次过河的人，所以先算出答案之后在来一遍输出路径

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int T, n;
 8 int a[1005];
 9 int main()
10 {
11     cin >> T;
12     while(T--)
13     {
14         cin >> n;
15         for(int i = 0; i < n; i++)cin >> a[i];
16         sort(a, a + n);
17         int i, tot = 0, sum = 0;
18         for(i = n - 1; i >= 3; i -= 2)//小于三人单独讨论 
19         {
20         //策略一：最快的和次快的先过河(时间a[1])，然后最快的回来送灯(a[0])，最慢的和次慢的过河a[i]，然后次快的回来送灯a[1]; 
21             int t1 = a[0] + 2 * a[1] + a[i];
22         //策略二：由最快的和最慢的过河(时间a[i])，然后最快的回来送灯(a[0])，次慢的和最慢的过河a[i-1]，然后最快的回来送灯a[0];
23             int t2 = 2 * a[0] + a[i - 1] + a[i];
24             sum += min(t1, t2);
25         }
26         int cases;
27         if(i == 2)sum += a[0] + a[1] + a[2], cases = 2;
28         else if(i == 1)sum += a[1], cases = 1;
29         else sum += a[0], cases = 0;
30         printf("%d
", sum);
31         for(int i = n - 1; i >= 3; i -= 2)
32         {
33             int t1 = a[0] + 2 * a[1] + a[i];
34             int t2 = 2 * a[0] + a[i - 1] + a[i];
35             if(t1 > t2)
36             {
37                 printf("%d %d
", a[0], a[i]);
38                 printf("%d
", a[0]);
39                 printf("%d %d
", a[0], a[i - 1]);
40                 printf("%d
", a[0]);
41             }
42             else
43             {
44                 printf("%d %d
", a[0], a[1]);
45                 printf("%d
", a[0]);
46                 printf("%d %d
", a[i - 1], a[i]);
47                 printf("%d
", a[1]);    
48             }
49         }
50         if(cases == 0)printf("%d
", a[0]);
51         else if(cases == 1)printf("%d %d
", a[0], a[1]);
52         else 
53         {
54             printf("%d %d
", a[0], a[2]);
55             printf("%d
", a[0]);
56             printf("%d %d
", a[0], a[1]);
57         }
58         if(T)cout<<endl;
59     }
60     return 0;
61 }