POJ-1700 Crossing River---过河问题（贪心）

题目链接：

https://vjudge.net/problem/POJ-1700

题目大意：

有N个人要渡河，但是只有一艘船，船上每次最多只能载两个人，渡河的速度由两个人中较慢的那个决定，小船来回载人直到所有人都渡河，求最短的渡河时间。

思路：

假设有速度最快的人a、速度次快的人b，速度最慢的人c，速度次慢的人d，把c和d送到终点考虑两种策略：

1、 a和b出发，a回来，c和d出发，b回来

2、 a和c出发，a回来，a和d出发，a回来

只需要比较这两种策略的快慢，每次选择较快的策略，当起点的人数少于4时直接处理，即可得出结果。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<set>
 6 #include<cmath>
 7 using namespace std;
 8 const int maxn = 1e4 + 10;
 9 typedef long long ll;
10 int T, n, m;
11 int a[maxn];
12 int main()
13 {
14     cin >> T;
15     while(T--)
16     {
17         cin >> n;
18         for(int i = 0; i < n; i++)
19         {
20             cin >> a[i];
21         }
22         sort(a, a + n);
23         int i = n - 1;
24         int ans = 0;
25         for(; i >= 3; i -= 2)
26         {
27         //策略一：最快的和次快的先过河(时间a[1])，然后最快的回来送灯(a[0])，最慢的和次慢的过河a[i]，然后次快的回来送灯a[1];
28             int time1 = a[1] + a[0] + a[i] + a[1];
29         //策略二：由最快的和最慢的过河(时间a[i])，然后最快的回来送灯(a[0])，次慢的和最慢的过河a[i-1]，然后最快的回来送灯a[0];
30             int time2 = a[i] + a[0] +a[i - 1] + a[0];
31             ans += min(time1, time2);
32         }
33         if(i == 2)ans += a[0] + a[1] + a[2];
34         else if(i == 1)ans += a[1];
35         else ans += a[0];
36         cout<<ans<<endl;
37     }
38     return 0;
39 }

进阶版：传送门