POJ 1700

题意

n个人要过河，一次只能同时两个人过河，两个人过河的时间取决于慢的一个。求最快的过河的时间

思路

先对过河速度进行升序排序。

然后分两种情况：

1. 最快的和最慢的先过去，然后由最快的一个人划回来，再由最快的次慢的，再由最快的划回来.
2. 最快的和次快的先划过去，然后由最快的先划回来，再由最慢的和次慢的过去，最后由次快的划回来。
   通过两种情况把最慢的和次慢的都送过河里，最快的和次快的都没过河。然后开始下一次迭代。

每一次选择最优解，即贪心算法。

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

int main(){
    int m,n,t[1001],i,sum;
    cin>>m;
    while(m--){
        cin>>n;
        sum = 0;
        for(i=0;i<n;i++){
            cin>>t[i];
        }
        sort(t,t+n);
        for(i = n-1;i>2;i -= 2){
            if(t[0]+2*t[1]+t[i]>2*t[0]+t[i-1]+t[i])
                sum += 2 * t[0] + t[i-1]+t[i];
            else
                sum +=t[0]+2*t[1]+t[i];
            if(i == 2) sum += t[0]+t[1]+t[2];
            else if(i == 1) sum +=t[1];
            else sum += t[0];
            cout<<sum<<endl;
        }
    }
    return 0;
}