POJ 1700
题意
n个人要过河，一次只能同时两个人过河，两个人过河的时间取决于慢的一个。求最快的过河的时间
思路
先对过河速度进行升序排序。
然后分两种情况：
- 最快的和最慢的先过去，然后由最快的一个人划回来，再由最快的次慢的，再由最快的划回来.
- 最快的和次快的先划过去，然后由最快的先划回来，再由最慢的和次慢的过去，最后由次快的划回来。
通过两种情况把最慢的和次慢的都送过河里，最快的和次快的都没过河。然后开始下一次迭代。
每一次选择最优解，即贪心算法。
#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;
}
