POJ 1700 Crossing River（贪心）

题意：过河问题、有N个人要渡河，但是只有一艘船，船上每次最多只能载两个人，渡河的速度由两个人中较慢的那个决定，小船来回载人直到所有人都渡河，求最短的渡河时间。
题目链接：http://poj.org/problem?id=1700
solution:贪心策略有两种
假设有速度最快的人a、速度次快的人b，速度最慢的人c，速度次慢的人d，把c和d送到终点考虑两种策略：
1、 a和b出发，a回来，c和d出发，b回来
2、 a和c出发，a回来，a和d出发，a回来
每次两种策略取较小者
当n为3、2、1时单独考虑

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		vector<int> a(n);
		for (int i = 0; i < n; ++i)scanf("%d", &a[i]);
		sort(a.begin(), a.end());
		int i = n - 1, ans = 0;
		//两种策略取其轻
		for (i; i >= 3; i -= 2)ans += min(a[1] * 2 + a[0] + a[i], a[i] + a[i - 1] + 2 * a[0]);
		if (i == 2) ans += a[0] + a[1] + a[2];//剩余三人则总过河时间就是这三人之和
		else if (i == 1)ans += a[1];//剩余两人
		else ans += a[0];//剩余一人
		printf("%d\n", ans);
	}
	return 0;
}