潜水最优策略

题目

一支队伍由n个人组成．在潜水时必须使用氧气瓶，但是每支队伍只有一个氧气瓶．最多两个人同时使用一个氧气瓶，但此时两人必须同步游泳，因此到达河对岸的时间等于较慢的一个单独游到终点所需要的时间．好在大家都很友好，因此任何两个人都愿意一起游泳．安排一种潜水策略，使得最后一名选手尽早到达终点。

Input

先输入一个整数n，表示队伍中人数，再依次输入每个人游到对岸所需时间（乱序）

Output

输出队伍到达河对岸最少的时间

Sample Input	Sample Output
3 1 3 4	8
6 1 2 5 6 8 9	27

算法

采用贪心算法的思想

• 在总人数（n）一定的前提下，过河次数也一定(2*n-3)

• 每次将最慢的两个人搭配在一起，以保证节约的时间最多

• 每次来回送氧气瓶由最快的两人负责

1. 每一组开始的时候是最快的两个人过去
2. 然后其中一人送瓶子回来
3. 然后最慢两人过去
4. 最后第二个快的人送瓶子回来

想法确定，我打算先列出几个例子，浅浅验证一下想法:（例子中已从小到大排好顺序）

测试样例

可以看到四个为一组，每一组分别为：第二人、第一人、每一次中最慢的人、第二人。其中每一组第三个人（也就是每一次最慢的人）的规律为从后往前的奇数位。

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    //input part
    int n;
    cin>>n;
    int arr[100];
    for (int i = 0; i < n; ++i) {
        cin>>arr[i];
    }
    
    if (n == 1){	//special process for only one people
        cout<<arr[0];
        return 0;
    }

    sort(arr,arr+n);

    int count = 2*n-3;  //times of crossing river
    int time = 0;       //the time used to cross river
    int control=0;      //used to choose the lowest person

    for (int i = 1; i <= count; i++) {
        int select = i % 4;     //four people compose a routine
        switch (select) {
            case 1:time += arr[1];
                break;
            case 2:time += arr[0];
                break;
            case 3:time += arr[n-1-control];
                control += 2;
                break;
            case 0:time += arr[1];
                break;
        }
    }
    cout<<time;
    return 0;
}

最后要说明一下，对于只有一个人的情况我单独处理了