/* * Crossing River * Time Limit: 1000MS Memory Limit: 10000K * Total Submissions: 7204 Accepted: 2580 * Description * A group of N people wishes to go across a river with only one boat, which can at most carry two persons. * Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth * so that all people may cross. Each person has a different rowing speed; the speed of a couple is * determined by the speed of the slower one. Your job is to determine a strategy that minimizes the * time for these people to get across.Input * The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each case contains N, and the second line contains N integers giving the time for each people to cross the river. Each case is preceded by a blank line. There won't be more than 1000 people and nobody takes more than 100 seconds to cross.Output * For each test case, print a line containing the total number of seconds required for all the N people to cross the river.Sample Input141 2 5 10Sample Output17SourcePOJ Monthly--2004.07.18
分析：纯粹逻辑问题。。。 */
#include <cstdlib> #include <iostream> using namespace std; /* * */ void qsort(int l,int r,int a[]) { int i=l,j=r,m=a[(l+r)>>1]; do { while(a[i]<m)i++; while(a[j]>m)j--; if(i<=j) { a[0]=a[i];a[i]=a[j];a[j]=a[0]; i++;j--; } }while(i<=j); if(i<r)qsort(i,r,a); if(l<j)qsort(l,j,a); } int main(int argc, char** argv) { int t; cin>>t; while(t>0) { int a[1001],n,ans=0; cin>>n; for(int i=1;i<=n;++i)cin>>a[i]; qsort(1,n,a); while(n>0) { if(n<3) { ans+=a[n]; n=0; } else if(n==3) { ans+=a[1]+a[2]+a[3]; n=0; } else { if((a[1]+a[n-1]<2*a[2])) ans+=(2*a[1]+a[n-1]+a[n]); else ans+=(2*a[2]+a[1]+a[n]); n-=2; } } cout<<ans<<endl; --t; } return 0; }
