题目大意
在一个晚上有N个人过河，他们总共只有一个手电筒，需要有手电筒才能过河，每次最多两个人同时过河，每个人的过河速度都不同，所以每次过河时间等于速度最慢的那个人的过河时间，让所有人全部过河，花费的时间最少是多少？
题解
如果只有一个人过河，那么过河的总时间就是这个人过河的时间。如果是两个人过河，那么总时间为过河速度较慢的那个人的过河时间。如果是三个人过河，假设速度从慢到快分别为a,b,c，分别用A,B,C表示三个人，那么我们会先让A和C一起过河，然后A返回，之后再让A和B一起过河，总花费时间为a+b+c。当人数大于等于4时，我们每次都让两个速度最慢的人过河，让这两个人过河我们有两种策略（其他过河方式的总时间和这两种策略的过河时间相同），假设A和B表示速度最快和第二快的人，速度分别为a,b，C和D表示速度最慢和第二慢的人，速度分别为c,d。第一种策略是：让A和B一起过河，A返回，C和D一起过河，B返回,花费的时间为2*b+a+c。第二种策略是：让A和C一起过河，A返回，A和D一起过河，A返回,时间花费为2*a+c+d。比较两个策略的时间花费，哪个时间花费短就选择哪个策略。
代码
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define MAXN 1005 5 int a[MAXN],q[2][MAXN*2]; 6 int n,m; 7 long total; 8 int compare(const void*a,const void*b) 9 { 10 return *(int*)a-*(int*)b; 11 } 12 void solve() 13 14 { 15 int i; 16 total=0; 17 m=-1; 18 for(i=n-1; i>=3; i-=2) 19 { 20 int t1=2*a[0]+a[i-1]+a[i]; 21 int t2=2*a[1]+a[0]+a[i]; 22 if(t1<t2) 23 { 24 m++; 25 q[0][m]=a[0];q[1][m]=a[i]; 26 m++; 27 q[0][m]=a[0]; 28 m++; 29 q[0][m]=a[0];q[1][m]=a[i-1]; 30 m++; 31 q[0][m]=a[0]; 32 total+=t1; 33 } 34 else 35 { 36 m++; 37 q[0][m]=a[0]; q[1][m]=a[1]; 38 m++; 39 q[0][m]=a[0]; 40 m++; 41 q[0][m]=a[i-1];q[1][m]=a[i]; 42 m++; 43 q[0][m]=a[1]; 44 total+=t2; 45 } 46 47 } 48 if(i==2) 49 { 50 total+=a[0]+a[1]+a[2]; 51 m++; 52 q[0][m]=a[0];q[1][m]=a[2]; 53 m++; 54 q[0][m]=a[0]; 55 m++; 56 q[0][m]=a[0];q[1][m]=a[1]; 57 } 58 else if(i==1) 59 { 60 total+=a[1]; 61 m++; 62 q[0][m]=a[0];q[1][m]=a[1]; 63 } 64 else 65 { 66 total+=a[0]; 67 m++; 68 q[0][m]=a[0]; 69 } 70 } 71 int main(void) 72 { 73 int T,i; 74 scanf("%d",&T); 75 while(T--) 76 { 77 scanf("%d",&n); 78 for(i=0; i<n; i++) 79 scanf("%d",&a[i]); 80 qsort(a,n,sizeof(a[0]),compare); 81 memset(q,0,sizeof(q)); 82 solve(); 83 printf("%ld\n",total); 84 for(i=0;i<=m;i++) 85 { 86 printf("%d",q[0][i]); 87 if(q[1][i]) 88 printf(" %d",q[1][i]); 89 printf("\n"); 90 } 91 if(T) printf("\n"); 92 } 93 return 0; 94 }