2440: 过桥问题
Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 1690  Solved: 398

Description
在漆黑的夜里，n位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，他们一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，每人所需要的时间分别是a1、a2、...an分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这些人尽快过桥。
Input
输入分2行第一行是一个整数n(1<=n<=1000) 第二行是n个整数，分别表示这n个人单独过桥需要的时间
Output
输出一行，他们过桥需要的总时间
Sample Input
5
1 3 6 8 12
Sample Output
29
HINT

Source
yhr

我的代码
#include<stdio.h>
int main()
{
    int t,m,i,j,n,a[1000],temp;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n-1;i++)//mao pao
    {
        for(j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
            {temp=a[i];a[i]=a[j];a[j]=temp;}
        }
    }
    m=n;
    t=0;
    while(n!=1)
    {
        t=t+a[1];
        n=n-2;//yu liang
        if(n!=0)
        {t=t+a[0];n++;}
        else
        {break;}
        t=t+a[m-1];
        m=m-2;
        n=n-2;
        if(n!=0)
        {t=t+a[1];n++;}
        else
        {break;}
    }
    if(n==1){printf("%d\n",a[0]);}
    else
    {printf("%d\n",t);}
    return 0;
}


运行数据没错，但提交总是WRONG ANSWER
求各位帮忙看下哪里有错，我找了很久都没找到

观摩。。。。。

目测, 你的算法...看不懂. 搞太复杂了.
简单点的就是:
1. 求最小值.
2. 把其它的值相加.

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    unsigned n;
    unsigned *a;    // 动态分配内存
    unsigned s = 0; // 求和.过桥的时间.
    int i, min;

    scanf("%d", &n);

    a = (int *)malloc(n*sizeof(int));
    if (a == NULL)
        exit(0);

    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (min = a[0], i = 1; i < n; i++) {
        if (a[i] >= min)   // 大于min的值求和.
            s += a[i];
        else {
            s += min;    // 有新的最小值.先把现在的min求和.
            min = a[i];  // 再将min赋最小值.
        }
    }
    if (n == 1)        // n == 1;
        s = a[0];
    printf("%d\n", s);
    free(a);      // 释放内存。
    return 0;
}

[ 本帖最后由 pangshch 于 2013-12-23 17:57 编辑 ]

让过桥时间最短的人拿手电筒, 不断接送.
因为他返回的时间最短. 所以最短时间就是其他人过桥时间的总和.

好像不是这样的，我记得我看过一篇帖子 有戏讲这个问题，好像是有两种情况。

刚刚有点仓促， 没有释放内存，也没有考虑n==1，
现在改了。
另外， 数据类型可以用short.节省内存。

动态内存是啥？你的程序里面有好多东西我没学到
我些的思路大概是，让最快的两人先过桥，然后走得最快的人回来送电筒，给桥这边走得最慢的两人过去，走得第二快的人又回来送电筒。。。这样循环知道所有人都过河。
我试的所有数据都对了，，所以不知道我的程序哪里有错TAT

层主，我最初也是这么想的，但是那么想如果按例子中结果是29的话，是忽略了从桥那边回来的时间的

程序运行是对的啊，楼主