在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。
输入 第一行是一个整数T(1<=T<=20)表示测试数据的组数 每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河 每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100) 输出 输出所有人都过河需要用的最少时间 样例输入 1 4 1 2 5 10 样例输出 17 思路：这是一个贪心问题，首先对数据进行排序。想要使过河时间时间最短，可以选用两种方式。 第一种：最快和次快的人先过去（用时T[1]），然后最快的人回来（用时T[0]）， 接着最慢和次慢的人过去（用时T[n-1]），最后次快的人回来（用时T[1]） 整理后为T[0] + T[1] + T[1] + T[n-1]。 尽量使两个花费时间相等的人一起过河，这样时间可能会小一点。 第二种：最快和最慢的过去（用时T[n-1]），然后最快的回来（用时T[0]）， 接着最快和次慢的人过去（用时T[n-2]）， 最后次快的人回来（用时T[0]）。整理后为T[0] + T[0] + T[n-1] + T[n-2]。 每次都使最快的回来，这样时间可能会小一点。 所以：每次比较这两种方法，选两种方式中时间的最短一种，这样最后过河时间一定最短。 代码： #include<stdio.h> #include<algorithm> using namespace std; /*void quicksort(int a[],int low,int high) { int i=low; int j=high; int temp=a[i]; if(low<high) { while(i<j) { while(i<j&&a[i]<a[j]) { j--; } a[i]=a[j]; while(i<j&&a[i]<=temp) { i++; } a[j]=a[i]; } a[i]=temp; quicksort(a,low,i-1); quicksort(a,j+1,high); } else { return ; } }*/快速排序的实现 int main() { int t; scanf("%d",&t); while(t--) { int n,a[1005],i,time=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); while(n>3) { int t1=a[0]+a[1]+a[1]+a[n-1];//方案一 int t2=a[0]+a[0]+a[n-1]+a[n-2];//方案二 time+=(t1>t2?t2:t1); n=n-2;//每次送走最慢的两个人 } if(n==1) { time+=a[0]; } if(n==2) { time+=a[1]; } if(n==3) { time+=a[0]+a[1]+a[2];//最快和次快的先过河，然后最快的回来，最后最快和最慢的一起过河 } printf("%d\n",time); } return 0; }