题目链接：http://acm.hust.edu.cn/vjudge/contest/122829#problem/A
题目大意：N个人夜里过河，总共只有一盏灯，每次最多过两个人，然后需要有人将灯送回
才能继续过人，每个人过桥都需要耗费一定的时间，让你求耗费的最少时间，并输出过河方案
首先，我们要明白一点，两个人过河肯定比只有一个人过河要来的划算，这样那个速度快的人
就相当于是被带过去的，然后我们从最简单的情况开始分析：（sort(a,a+n))
n=1时,直接过去就可以，t=a[0]
n=2时，两个人直接一起过去，耗时t=a[1]
n=3时,因为肯定要有人送灯回来，肯定是选择跑的最快的a[0]
所以方案是 0,1->0->0,2耗时a[0]+a[1]+a[2]
当n>=4时，我们有两种可能最优方案，
1.全都让a[0]来送，送过去以后送灯回来耗时： a[i]+a[i+1]+2*a[0]
2.0，1->0->i,i+1->1 耗时：a[i+1]+2*a[1]+a[0]
比较选择最优方案
tips:注意输出格式，除了最后一个case，其他都要输出两个换行
代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int maxn=1500; int a[maxn]; int main() { int T; int n; int i; scanf("%d",&T); // printf(" "); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int sum=0; int p=n; int t; for(i=n-1;i>=3;i-=2) { int t1=2*a[0]+a[i]+a[i-1]; int t2=2*a[1]+a[0]+a[i]; //cout<<t1<<" "<<t2<<endl; sum+=min(t1,t2); } //cout<<sum<<endl; if(i==0) sum+=a[0]; else if(i==1) sum+=a[1]; else sum=sum+a[0]+a[1]+a[2]; printf("%d ",sum); for(int i=n-1;i>=3;i-=2) { int t1=2*a[0]+a[i]+a[i-1]; int t2=2*a[1]+a[0]+a[i]; if(t1<t2) { printf("%d %d ",a[0],a[i]); printf("%d ",a[0]); printf("%d %d ",a[0],a[i-1]); printf("%d ",a[0]); } else { printf("%d %d ",a[0],a[1]); printf("%d ",a[0]); printf("%d %d ",a[i-1],a[i]); printf("%d ",a[1]); } } if(i==1) printf("%d %d ",a[0],a[1]); else if(i==2) { printf("%d %d ",a[0],a[1]); printf("%d ",a[0]); printf("%d %d ",a[0],a[2]); } else printf("%d ",a[0]); if(T) cout<<endl; } return 0; }