首页 > 代码库 > poj 1700 Crossing River(贪心)

poj 1700 Crossing River(贪心)

分析:题意

源岸数量<=3  很好判断 3:num[0]+num[1]+num[2] 2:num[1] ,1:num[0]

源岸数量>3

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int main(void){    int n,t ;    int i,j;    int num[1001];    cin>>t;    while(t--){        cin>>n;        for(i=0;i<n;i++) cin>>num[i];        sort(num,num+n);        int cnt=n,sum=0;        while(cnt>3){            int w1=num[0]+2*num[1]+num[cnt-1],w2=2*num[0]+num[cnt-2]+num[cnt-1];            sum+=min(w1,w2);            cnt-=2;        }        if(cnt==3) sum+=num[0]+num[1]+num[2];        else if(cnt==2) sum+=num[1];        else sum+=num[0];        cout<<sum<<endl;    }    return 0;}

 

poj 1700 Crossing River(贪心)