POJ1700 Crossing River（贪心）

题意：

经典的过河问题，一群人要过河，只有一艘船，船最多坐两个人，船速为两人中较慢的那个，问把所有人都运到对岸最少要多长时间。

要点：

这题自己想真挺难，看了一下网上的方法，基本上是这样，当人数n=1,2,3时，最小时间是固定的，而n大于3时，可以先考虑把最慢的两个人运过去，有以下两种方法：一：用最快的人先把最慢的运过去，再自己划船回来，再把次慢的运过去，再自己回来；二：最快的和次快的先划船过去，最快的回来，最慢的和次慢的再划过去，最后次快的回来。这两种花费时间不同，但都是把最慢的两个运过去，所以我们只要两个两个比较得出相对小的贪心，最后剩下小于三个人就行了。

#include<iostream>
#include<algorithm>
using namespace std;
int per[1005];int part(int n)
{switch (n){case 1:return per[0];case 2:return per[1];case 3:return per[0] + per[1] + per[2];}
}int main()
{int T,n;cin >> T;while (T--){cin >> n;for (int i = 0; i < n; i++)cin >> per[i];sort(per, per + n);int time = 0;while (n > 3){int a = per[0];int b = per[1];int x = per[n - 1];int y = per[n - 2];time += min(2 * a + x + y, 2 * b + a + x);n -= 2;}time += part(n);cout << time << endl;}return 0;
}