题意：过河问题、有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; }