对于这一类问题，我们首先想到的就是用贪心算法。 我们可以让时间最长的两个人过河，但是怎么做才能把时间变为最短呢？是用时间最短的人一个一个送过去，还是怎么样呢？ 其实，我们可以考虑两种方法：1.让时间最短的人一个一个的送过去；2.先要两个时间最短的过去，然后一个回来送电灯，然后让两个时间最长的人过去，再要对面时间最短的人把电灯送回来，以此类推； 我们要做的就是在这两种方法中选择一种过河。 代码如下：
#include<stdio.h> void sort(int *a,int left,int right){ if(left>=right) return; int i,j,t; i=left,j=right,t=a[left]; while(i<j){ while(i<j&&a[j]>=t)j--; a[i]=a[j]; while(i<j&&a[i]<=t)i++; a[j]=a[i]; } a[i]=t; sort(a,left,i-1); sort(a,i+1,right); } int main(){ int N; scanf("%d",&N); while(N--){ int n,a[1010],i,sum=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,0,n-1); while(n>3){ if((a[n-1]+a[0]+a[n-2]+a[0])>(a[n-1]+a[1]+a[1]+a[0])) sum+=a[n-1]+a[1]+a[1]+a[0]; else sum+=a[n-1]+a[0]+a[n-2]+a[0]; n=n-2; } if(n==3) sum+=a[0]+a[1]+a[2]; else if(n==2) sum+=a[1]; else sum+=a[0]; printf("%d\n",sum); } return 0; }