1232：Crossing River——贪心

【题目描述】
几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。

【输入】
输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。

【输出】
输出t行数据，每行1个数，表示每组过河最少时间。

【输入样例】
1
4
1 2 5 10
【输出样例】
17

分析

1. 此题的贪心的思想就是，每次让最慢的两个人到达终点，进行多组操作，至到所有人都到终点；
2. 每组的操作的策略就是：让当前剩下的人中，最慢的两个人过去；然后用这个策略重复进行几组操作（每组操作剩余的人减2），至到剩下的人小于4（因为这个策略每组操作都需要4个人）；
3. . 每组的操作有两种策略：

• 策略1：
  当前剩余的人中，让最快的分两趟带最慢的a[n],a[n-1]； 模拟过程就是：a[1]和a[n]先过河（用时a[n]），然后a[1]回来（用时a[1]），然后a[1]带a[n-1]过河（用时a[n-1]），最后a[1]再回来（用时a[1]），总用时：a[n]+a[1]+a[n-1]+a[1]；
• 策略2：
  让a[n]和a[n-1]一起过，通过a[1]和a[2]来送船； 最快的a[1]和次快的a[2]先过去（用时a[2]），然后最快的a[1]回来（用时a[1]），然后a[n-1]和a[n]再过去（用时a[n]），最后a[2]再回来（用时a[2]），总用时：a[2]+a[1]+a[n]+a[2]；

4. 我们正常思想也就是第一想法就是快的带慢的，也就是第一种策略，但是发现样例多过不去，这时候我们也要想另一个策略，直接让a[n]和a[n-1]一起过，通过a[1]和a[2]来送船（a[1]a[2]先把a[2]送过去，然后a[1]送船让a[n]a[n-1]过河，让a[2]再送船回来）；
5. 最后特判n=3，n=2;
6. 需要注意过河时间是两者之间最大值，不是他两加起来，比如a[1]和a[n]一起，刚开始直接算a[1]+a[n]了，应该是只算a[n]；

#include

using namespace std;

int t, n;
int a[1000];

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        sort(a + 1, a + 1 + n);
        int ans = 0;
        //这种策略至少需要4个人
        while (n >= 4) {
            //两种策略取最优
            //当前剩余的人中，最快的 分两趟带最慢的a[n],a[n-1]
            int time1 = (a[n] + a[1] + a[n - 1] + a[1]);
            //最快的a[1]和次快的a[2]先过去，然后最快的a[1]回来,a[n-1]和a[n]再过去，a[2]再回来
            int time2 = (a[2] + a[1] + a[n] + a[2]);
            ans += min(time1, time2);
            //已经运走剩下的人中，最慢的和次慢的了
            n -= 2;
        }
        if (n == 3) {
            //第一种策略最优
            ans += (a[n] + a[1] + a[n - 1]);
        } else if (n == 2) {
            //直接过
            ans += a[2];
        }
        cout << ans << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38