POJ 1700

題意

n個(gè)人要過(guò)河，一次只能同時(shí)兩個(gè)人過(guò)河，兩個(gè)人過(guò)河的時(shí)間取決于慢的一個(gè)。求最快的過(guò)河的時(shí)間

思路

先對(duì)過(guò)河速度進(jìn)行升序排序。

然后分兩種情況：

1. 最快的和最慢的先過(guò)去，然后由最快的一個(gè)人劃回來(lái)，再由最快的次慢的，再由最快的劃回來(lái).
2. 最快的和次快的先劃過(guò)去，然后由最快的先劃回來(lái)，再由最慢的和次慢的過(guò)去，最后由次快的劃回來(lái)。
   通過(guò)兩種情況把最慢的和次慢的都送過(guò)河里，最快的和次快的都沒過(guò)河。然后開始下一次迭代。

每一次選擇最優(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;
}