POJ 1700
題意
n個(gè)人要過(guò)河，一次只能同時(shí)兩個(gè)人過(guò)河厚脉，兩個(gè)人過(guò)河的時(shí)間取決于慢的一個(gè)央拖。求最快的過(guò)河的時(shí)間
思路
先對(duì)過(guò)河速度進(jìn)行升序排序。
然后分兩種情況：
- 最快的和最慢的先過(guò)去垮卓，然后由最快的一個(gè)人劃回來(lái)垫桂，再由最快的次慢的，再由最快的劃回來(lái).
- 最快的和次快的先劃過(guò)去粟按，然后由最快的先劃回來(lái)诬滩，再由最慢的和次慢的過(guò)去，最后由次快的劃回來(lái)灭将。
通過(guò)兩種情況把最慢的和次慢的都送過(guò)河里疼鸟，最快的和次快的都沒(méi)過(guò)河。然后開(kāi)始下一次迭代庙曙。
每一次選擇最優(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;
}
