POJ 1700
題意
n個人要過河潜索，一次只能同時兩個人過河，兩個人過河的時間取決于慢的一個懂酱。求最快的過河的時間
思路
先對過河速度進行升序排序竹习。
然后分兩種情況：
- 最快的和最慢的先過去，然后由最快的一個人劃回來列牺，再由最快的次慢的由驹，再由最快的劃回來.
- 最快的和次快的先劃過去，然后由最快的先劃回來昔园，再由最慢的和次慢的過去，最后由次快的劃回來并炮。
通過兩種情況把最慢的和次慢的都送過河里默刚，最快的和次快的都沒過河。然后開始下一次迭代逃魄。
每一次選擇最優(yōu)解荤西，即貪心算法。
#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;
}
