漆黑的夜里，n位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，他们一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，每人所需要的时间分别是a1、a2、...an分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这些人尽快过桥。
#include<stdio.h>
int main()
{
    int n,a[100],i,m=0,s,j,t;
    while(scanf("%d",&n)!=0)
    {
        s=0;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            for(j=1+i;j<n;j++)
            if(a[j]<a[i])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        if(n%2==0)
        {for(i=n-1;i>=1;i=i-2)
        s=s+a[i];
        s=s+(n-2)*a[1]+a[0]*(n-2)/2;
        printf("%d\n",s);}
        else
        {for(i=n-1;i>=0;i=i-2) s=s+a[i];
        
        s=s+(n-3)*a[1]+a[0]*(n-3)/2+a[1];
        printf("%d\n",s);}   
    }
    return(0);
}

首先，你的算法不对。有n个人过桥，所需时间最短为除了用时最短的人以外的n－1个人的用时之和，加上用时最短人的时间×（n－2）；
其次，用while(scanf("%d",&n)!=0)这句语句的话，最后要输入一个0才能停止。
最后，整个语句在输入界面没有任何提示，不便于外人使用。
以下程序供参考。

#
include<stdio.h>
int main()
{
    int n,a[100]={0},i,s,j,t;
    printf("请输入过桥人数n：");
    scanf("%d",&n);
    if(n!=0)
    {
        s=0;
    printf("请分别输入n个人的过桥所需时间：\n");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            for(j=1+i;j<n;j++)
            if(a[j]<a[i])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        for(i=n-1;i>0;i--)
        s=s+a[i];
        s=s+(n-2)*a[0];
        printf("共需用时%d分钟。\n",s);    
    }
    else printf("输入错误。\n");
}

之前有点小错误， for(i=n-1;i>0;i--)里面i要大于0，不能等于0。

[ 本帖最后由 luchar 于 2011-11-8 10:23 编辑 ]

你的算法明显不对，不信你可以测试一下你的算法和我的算法用的总时间...

三个人过河 时间分别为1 2 3 你的程序输出了7 应该是1和2过为2 1再回来 为3  然后1和3过3 1不会来为0

总共用时应该为6

#include<stdio.h>
int main()
{
    int n,a[100]={0},i,s,j,t;
    printf("请输入过桥人数n：");
    scanf("%d",&n);
    if(n!=0)
    {
        s=0;
    printf("请分别输入n个人的过桥所需时间：\n");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        if(1 == n)
        {
            printf("共需用时%d分钟。\n",a[0]);  
            return 0;
        }
        for(i=0;i<n;i++)
        {
            for(j=1+i;j<n;j++)
            if(a[j]<a[i])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
        for(i=1;i<n-1;i++)
            s+=a[i]+a[0];
        s+=a[i];
        printf("共需用时%d分钟。\n",s);   
    }
    else printf("输入错误。\n");
} 

[ 本帖最后由 laoyang103 于 2011-11-8 14:55 编辑 ]

只有一个手电筒，
是1和2或3过去，还要把手电筒送回来，1回来，再和剩下的那个过去

[ 本帖最后由 luchar 于 2011-11-8 10:24 编辑 ]

“
首先，你的算法不对。有n个人过桥，所需时间最短为除了用时最短的人以外的n－1个人的用时之和，加上用时最短人的时间×（n－2）；
”

就这句话就已经说明你的算法错了。

给你一个面试的题目：
“
有一家人，晚上要过一个独木桥。但是他们只有一盏灯，而这盏灯只能使用30秒了。要在灯熄灭前过这座桥，他们一家五口人每个人过桥的速度不同。瘦人1秒，小胖3秒，姑娘6秒，大胖8秒，瘸子12秒。 每次只能过两个人。 过去后，对岸要有一个人再把灯送回来。
”

如果按照你的算法 是不是时间为 12 + 8 + 6 + 3 + 1 * （5 - 2） = 32？
其实这个最短时间是29

你可以通过这个游戏来验证：
http://www.

[ 本帖最后由 yuccn 于 2011-11-8 13:02 编辑 ]

看了这么多，有没有人知道正确的算法

我的时间是6，我是这样想得，先把n个人从小到大进行排序，然后，a0,a1过去，a0回来，然后an-1,an-2过去，a1回来，接下来依次类推...

你的数字和我的题目的例子是一样的说，他是这样算的，3+1+12+3+3+1+6=29，我的算法跟这差不多...

呵呵，如果你的算法算的是29 ，那说明你的算法是对的

我没有测试。^_^